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.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4#include <iostream>
5using namespace std;
vector<int> frequencySort(vector<int>& nums) {
unordered_map<int, int> freq;
int maxFreq = 0;
for (int num : nums) {
freq[num]++;
maxFreq = max(maxFreq, freq[num]);
}
vector<vector<int>> buckets(maxFreq + 1);
for (auto& [num, count] : freq) {
buckets[count].push_back(num);
}
vector<int> result;
for (int i = 1; i <= maxFreq; ++i) {
sort(buckets[i].rbegin(), buckets[i].rend());
for (int num : buckets[i]) {
result.insert(result.end(), i, num);
}
}
return result;
}
int main() {
vector<int> nums = {1, 1, 2, 2, 2, 3};
vector<int> sorted = frequencySort(nums);
for (int num : sorted) {
cout << num << " ";
}
// Output: 3 1 1 2 2 2
return 0;
}This approach constructs frequency buckets, where each index in the bucket corresponds to the frequency of numbers. Each bucket contains numbers with identical frequencies. For each frequency bucket, we sort numbers in decreasing order, fulfilling the condition of the problem, and append them to the result.