排序應用: 依照頻率排列元素 Sort Array by Increasing Frequency_LC #1636

Meriç Dağlı on Unsplash

題目敘述 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之間。

演算法 客製化排序

依照題目敘述，有兩個排序條件

1. 出現頻率由小到大
2. 若頻率相同時，依照元素數值從大到小。

先建立一個字典，統計每個元素的出現次數。

接著呼叫排序function，並且傳入這兩條排序條件，進行客製化排序。

# 1. ​num_occ_dict[x] 代表出現頻率由小到大
# 2. -x代表 若頻率相同時，依照元素數值從大到小。

key=lambda x:(num_occ_dict[x], -x) )

Python sort with key 客製化排序的教學

程式碼 客製化排序

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)的空間。

Reference:

[1] Sort Array by Increasing Frequency - LeetCode