Given an integer array, sort the array according to the frequency of elements in decreasing order, if the frequency of two elements are same then sort in increasing orderĀ
Examples:
Input: arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}
Output: 3 3 3 3 2 2 2 12 12 4 5
Explanation :
No. Freq
2 : 3
3 : 4
4 : 1
5 : 1
12 : 2
Input: arr[] = {4, 4, 2, 2, 2, 2, 3, 3, 1, 1, 6, 7, 5}
Output: 2 2 2 2 1 1 3 3 4 4 5 6 7
Different approaches have been discussed in below posts:Ā
Sort elements by frequency | Set 1Ā
Sort elements by frequency | Set 2
Ā Sorting Array Elements By Frequency | Set 3 (Using STL)Ā
Sort elements by frequency | Set 4 (Efficient approach using hash)Ā
Approach:Ā
Java Map has been used in this set to solve the problem.Ā
The java.util.Map interface represents a mapping between a key and a value. The Map interface is not a subtype of the Collection interface. Therefore it behaves a bit different from the rest of the collection types.Ā
Ā In the below program:
- Get the element with its count in a Map
- By using the Comparator Interface, compare the frequency of an elements in a given list.
- Use this comparator to sort the list by implementing Collections.sort() method.
- Print the sorted list.
Implementation:Ā
Java
import java.util.*;Ā
public class GFG {Ā
Ā Ā Ā Ā // Driver CodeĀ Ā Ā Ā public static void main(String[] args)Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Declare and Initialize an arrayĀ Ā Ā Ā Ā Ā Ā Ā int[] array = { 4, 4, 2, 2, 2, 2, 3, 3, 1, 1, 6, 7, 5 };Ā
Ā Ā Ā Ā Ā Ā Ā Ā Map<Integer, Integer> map = new HashMap<>();Ā Ā Ā Ā Ā Ā Ā Ā List<Integer> outputArray = new ArrayList<>();Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Assign elements and their count in the list and mapĀ Ā Ā Ā Ā Ā Ā Ā for (int current : array) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int count = map.getOrDefault(current, 0);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā map.put(current, count + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā outputArray.add(current);Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Compare the map by valueĀ Ā Ā Ā Ā Ā Ā Ā SortComparator comp = new SortComparator(map);Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Sort the map using Collections CLassĀ Ā Ā Ā Ā Ā Ā Ā Collections.sort(outputArray, comp);Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Final OutputĀ Ā Ā Ā Ā Ā Ā Ā for (Integer i : outputArray) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.print(i + " ");Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }}Ā
// Implement Comparator Interface to sort the valuesclass SortComparator implements Comparator<Integer> {Ā Ā Ā Ā private final Map<Integer, Integer> freqMap;Ā
Ā Ā Ā Ā // Assign the specified mapĀ Ā Ā Ā SortComparator(Map<Integer, Integer> tFreqMap)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā this.freqMap = tFreqMap;Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Compare the valuesĀ Ā Ā Ā @OverrideĀ Ā Ā Ā public int compare(Integer k1, Integer k2)Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Compare value by frequencyĀ Ā Ā Ā Ā Ā Ā Ā int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Compare value if frequency is equalĀ Ā Ā Ā Ā Ā Ā Ā int valueCompare = k1.compareTo(k2);Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If frequency is equal, then just compare by value, otherwise -Ā Ā Ā Ā Ā Ā Ā Ā // compare by the frequency.Ā Ā Ā Ā Ā Ā Ā Ā if (freqCompare == 0)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return valueCompare;Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return freqCompare;Ā Ā Ā Ā }} |
2 2 2 2 1 1 3 3 4 4 5 6 7
Time Complexity: O(n Log n)
Space complexity: The space complexity of the above code is O(n) as we are using a hashmap and an arraylist of size n.
