題目敘述 Sort Array by Increasing Frequency Leetcode #1636
給定一個輸入陣列，請依照出現頻率的多寡從低頻到高頻排列陣列元素。
如果有兩個元素的出現頻率相同，依照元素大小從大到小排列。
測試範例
Example 1:Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.
Example 2:
Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.
Example 3:
Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]
約束條件
Constraints:
1 <= nums.length <= 100
輸入陣列長度介於1~100。
-100 <= nums[i] <= 100
每個陣列元素介於-100 ~ 100之間。
演算法 客製化排序
依照題目敘述，有兩個排序條件
- 出現頻率由小到大
- 若頻率相同時，依照元素數值從大到小。
先建立一個字典，統計每個元素的出現次數。
接著呼叫排序function，並且傳入這兩條排序條件，進行客製化排序。
# 1. num_occ_dict[x] 代表出現頻率由小到大
# 2. -x代表 若頻率相同時，依照元素數值從大到小。
key=lambda x:(num_occ_dict[x], -x) )
程式碼 客製化排序
from collections import Counter
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
# key: distinct number
# value: frequency of number
num_occ_dict = Counter(nums)
# Sort number by pair of (frequency, and negative value)
nums.sort( key=lambda x:(num_occ_dict[x], -x) )
return nums
複雜度分析
時間複雜度: O( n log n)
時間成本落在排序，所需時間為O(n log n)
空間複雜度: O(n)
建立字典，需要額外O(n)的空間。
