How to Sort Array by Frequency in Java

The challenge

Sort elements in an array by decreasing frequency of elements. If two elements have the same frequency, sort them by increasing value.

Solution.sortByFrequency(new int[]{2, 3, 5, 3, 7, 9, 5, 3, 7}); // Returns {3, 3, 3, 5, 5, 7, 7, 2, 9} // We sort by highest frequency to lowest frequency. // If two elements have same frequency, we sort by increasing value.
Code language: JavaScript (javascript)

The solution in Java code

Option 1:

import java.util.*; public class Solution { public static int[] sortByFrequency(int[] array) { Map<Integer,Integer> freq = new HashMap<>(); List<Integer> list = new ArrayList<>(); for (int a : array) { freq.put(a, freq.getOrDefault(a, 0) + 1); list.add(a); } Collections.sort(list, new Comparator() { public int compare(Object o1, Object o2) { Integer i1 = (Integer)o1, i2 = (Integer)o2; Integer f1 = freq.get(i1), f2 = freq.get(i2); int f = f2.compareTo(f1); return f == 0 ? i1.compareTo(i2) : f; }}); return list.stream().mapToInt(i -> i).toArray(); } }
Code language: Java (java)

Option 2:

import java.util.*; import java.util.function.Function; import java.util.stream.Collectors; import java.util.stream.IntStream; import java.util.stream.Stream; public class Solution { public static int[] sortByFrequency(int[] array) { return IntStream.of(array) .boxed() .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) .entrySet() .stream() .sorted(Comparator.comparingLong(i -> ((Map.Entry<Integer,Long>)i).getValue()) .reversed() .thenComparingLong(i -> ((Map.Entry<Integer,Long>)i).getKey())) .flatMapToInt(i -> Stream.generate(i::getKey) .limit(i.getValue()) .mapToInt(Integer::intValue)) .toArray(); } }
Code language: Java (java)

Option 3:

import java.util.*; import java.util.function.Function; import java.util.stream.Collectors; public class Solution { public static int[] sortByFrequency(int[] array) { System.out.println(Arrays.toString(array)); Map<Integer, Long > fr = Arrays.stream(array).boxed().collect(Collectors.groupingBy(Function.identity(),Collectors.counting())); return Arrays.stream(array).boxed().sorted(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { int c = Integer.compare((int)(long)fr.get(o2),(int)(long)fr.get(o1)); return c==0?Integer.compare(o1,o2):c; } }).mapToInt(x->x).toArray(); } }
Code language: Java (java)

Test cases to validate our solution

import org.junit.Test; import static org.junit.Assert.assertArrayEquals; import org.junit.runners.JUnit4; public class SolutionTest { @Test public void basicTests() { assertArrayEquals(new int[]{3, 3, 3, 5, 5, 7, 7, 2, 9}, Solution.sortByFrequency(new int[]{2, 3, 5, 3, 7, 9, 5, 3, 7})); assertArrayEquals(new int[]{1, 1, 1, 0, 0, 6, 6, 8, 8, 2, 3, 5, 9}, Solution.sortByFrequency(new int[]{1, 2, 3, 0, 5, 0, 1, 6, 8, 8, 6, 9, 1})); assertArrayEquals(new int[]{9, 9, 9, 9, 4, 4, 5, 5, 6, 6}, Solution.sortByFrequency(new int[]{5, 9, 6, 9, 6, 5, 9, 9, 4, 4})); assertArrayEquals(new int[]{1, 1, 2, 2, 3, 3, 4, 4, 5, 8}, Solution.sortByFrequency(new int[]{4, 4, 2, 5, 1, 1, 3, 3, 2, 8})); assertArrayEquals(new int[]{0, 0, 4, 4, 9, 9, 3, 5, 7, 8}, Solution.sortByFrequency(new int[]{4, 9, 5, 0, 7, 3, 8, 4, 9, 0})); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments