Given an array nums of integers, you need to sort the array in increasing order based on the frequency of the values. If two values have the same frequency, sort them in decreasing order.
Table of Contents
Sample Input and Expected Output:
Input:
nums = [1, 1, 2, 2, 2, 3]
Output:
Sorted array by increasing frequency: [3, 1, 1, 2, 2, 2]
Input:
nums = [2, 3, 1, 3, 2]
Output:
Sorted array by increasing frequency: [1, 3, 3, 2, 2]
Solution in C++:
The idea is to use a hash map to count the frequency of each element in the array. Then, we sort the elements based on their frequencies. To handle the case of the same frequency, we use a custom comparator that sorts the elements in decreasing order if their frequencies are the same.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
std::vector<int> frequencySort(std::vector<int>& nums) {
std::unordered_map<int, int> freqMap;
// Count the frequency of each element in the array.
for (int num : nums) {
freqMap[num]++;
}
// Sort the elements based on frequencies and handle the same frequency case.
std::sort(nums.begin(), nums.end(), [&](int a, int b) {
if (freqMap[a] != freqMap[b]) {
return freqMap[a] < freqMap[b]; // Sort by increasing frequency.
} else {
return a > b; // Sort in decreasing order if frequencies are the same.
}
});
return nums;
}
int main() {
std::vector<int> nums1 = {1, 1, 2, 2, 2, 3};
std::vector<int> nums2 = {2, 3, 1, 3, 2};
std::vector<int> result1 = frequencySort(nums1);
std::vector<int> result2 = frequencySort(nums2);
std::cout << "Sorted array by increasing frequency: [";
for (int num : result1) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
std::cout << "Sorted array by increasing frequency: [";
for (int num : result2) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(n log n), where n is the size of the input vector nums. This is because we are using std::sort() to sort the elements based on their frequencies, which takes O(n log n) time.
The space complexity is O(n) as we are using a hash map to store the frequency of each element. The size of the hash map is at most n, where n is the number of unique elements in the input array. The sorting operation is performed in-place on the input vector, so it does not require any additional space.