Sponsored
Sponsored
This approach involves creating a frequency map for all the numbers in the array. Then, sort the numbers based on their frequency, with a secondary sort order for numbers with the same frequency in decreasing numeric order.
Time Complexity: O(N log N), where N is the number of elements in nums, due to sorting.
Space Complexity: O(N), for storing the frequency map.
1from collections import Counter
2
3def frequencySort(nums):
4 freq = Counter(nums)
5 return sorted(nums, key=lambda x: (freq[x], -x))
6
7# Example usage:
8nums = [1, 1, 2, 2, 2, 3]
9print(frequencySort(nums)) # Output: [3, 1, 1, 2, 2, 2]The solution uses the Counter from the collections module to count the frequency of each number in nums. Then, it sorts the numbers using a custom key: the primary key is the frequency, and the secondary key is the negative of the number to ensure decreasing order when frequencies match.
This approach uses a bucket sort strategy by grouping numbers into buckets based on their frequencies, then sorting within each bucket based on the requirement of decreasing order for equal frequency numbers.
Time Complexity: O(N + K log K), where N is the number of elements and K is the number of distinct elements, due to bucket sorting and sorting each bucket.
Space Complexity: O(N + K), for buckets and frequency storage.
1function frequencySort(nums) {
2 const
This JavaScript solution operates similarly to the described C++ solution, using an object to track the frequency of numbers and a bucket to group numbers by frequency. It sorts numbers within each bucket in descending order before constructing the final result array.