Hash Table with Custom Compare Function | C++, Python, Java
Approach\n Describe your approach to solving the problem. \nWe can use a hashmap (or an array) freq to map each value in nums to their frequencies, then use a c
# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use a hashmap (or an array) `freq` to map each value in `nums` to their frequencies, then use a custom compare function to sort them based on their frequencies. For the custom compare function we must remember that if two numbers have the same frequency, the greater one comes first in the sorted list. Otherwise, all the values are sorted by increasing frequency.\n# Complexity\n- Time complexity: $$O(n(log(n)))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<int> frequencySort(vector<int>& nums) {\n        int freq[201] = {}; // Array to store frequency of each number\n        // Guaranteed to be -100 to 100 so we add 100 for negative numbers\n        for (int num : nums)\n            freq[num + 100]++;\n        sort(nums.begin(), nums.end(), [&freq](int a, int b){\n            return freq[a + 100] == freq[b + 100] ? a > b : freq[a + 100] < freq[b + 100];\n        }); // If the frequency of a and b are equal, we compare the values, otherwise we compare the frequencies and return the lesser one\n        return nums;\n    }\n};\n```\n```python []\nclass Solution:\n    def frequencySort(self, nums: List[int]) -> List[int]:\n        freq = Counter(nums) # Returns a dictionary with every unique element in nums mapped to their frequency in the list\n        return sorted(nums, key=lambda x: (freq[x], -x)) # Returns a tuple in the form (frequency, -value).\n        # This sorts first by frequency, but if they are equal, it then compares\n        # the values. However, we change to negative so larger values will be first since it sorts in ascending order by default\n```\n```Java []\nclass Solution {\n    public int[] frequencySort(int[] nums) {\n        int[] freq = new int[201]; // Array to store frequency of each number\n        // Guaranteed to be -100 to 100 so we add 100 for negative numbers\n        List<Integer> list = new ArrayList<>(); // Array list so we can use a custom copare functions with the sort methods in the collections class\n        for (int num : nums){\n            freq[num + 100]++;\n            list.add(num);\n        }\n        Collections.sort(list, (a, b) -> {\n            return freq[a + 100] == freq[b + 100] ? b - a : freq[a + 100] - freq[b + 100];\n        }); // If the frequency of a and b are equal, we compare the values, otherwise we compare the frequencies and return the lesser one\n        for (int i = 0; i < nums.length; i++)\n            nums[i] = list.get(i);\n        return nums;\n    }\n}\n```\n
['Array', 'Hash Table', 'C', 'Sorting', 'Python', 'C++', 'Java', 'Python3']