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.
1import java.util.*;
2
3class Solution {
4 public int[] frequencySort(int[] nums) {
5 Map<Integer, Integer> freq = new HashMap<>();
6 for (int n : nums) {
7 freq.put(n, freq.getOrDefault(n, 0) + 1);
8 }
9 return Arrays.stream(nums)
10 .boxed()
11 .sorted((a, b) -> freq.get(a) != freq.get(b) ? freq.get(a) - freq.get(b) : b - a)
12 .mapToInt(Integer::intValue)
13 .toArray();
14 }
15
16 public static void main(String[] args) {
17 Solution solution = new Solution();
18 int[] nums = {1, 1, 2, 2, 2, 3};
19 System.out.println(Arrays.toString(solution.frequencySort(nums))); // Output: [3, 1, 1, 2, 2, 2]
20 }
21}This solution uses a HashMap to store the frequency of each number. It then converts the array to a stream of Integers, sorts it using a custom comparator, and finally converts it back to an array. The comparator prioritizes frequency and, in case of ties, the value itself in decreasing order.
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.