Given an array of integers nums
, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
Return the sorted array.
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
-100 <= nums[i] <= 100
Solution: Hashtable + Sorting
Use a hashtable to track the frequency of each number.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: vector<int> frequencySort(vector<int>& nums) { unordered_map<int, int> freq; for (int x : nums) ++freq[x]; sort(begin(nums), end(nums), [&](int a, int b) { if (freq[a] != freq[b]) return freq[a] < freq[b]; return a > b; }); return nums; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment