Suppose I have an array of integers:

[ 1,2,3,4,5,6,1,2,3,1,2... ]

I want to know the K most frequent elements. The phrase "K most frequent" immediately makes me think of a Max Heap data structure, so I've decided to create a custom object to both count and prioritize elements:

public class countedInts implements Comparable<countedInts>{
    public int theInt, count;
    public countedInts(int a, int b) {
        this.theInt = a;
        this.count = b;
    }
    @Override
    public int compareTo(countedInts o) {
        return this.count - o.count;
    }
}

This object is essentially two ints, paired together. Simple.

Okay: now for the main code:

public int[] topKFreq(int[] arr, int k) {

    PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for( int i=0; i<arr.length; i   ) {
        // If arr[i] is not tracked with a countedInts object:
            maxHeap.offer( new countedInts(arr[i], 1) );
        // But if arr[i] is already stored within a countedInts object...
            countedInts tmp = maxHeap.get( ??? );
            tmp.count  ;
            maxHeap.offer( tmp );
    }
}

You see the problem. As I consider the elements in arr, I need a way to check maxHeap to see if I have an countedInts object already checking the element. I need to look at the member of the object within the PriorityQueue. Is there a way to do this? Or is there a better strategy to this problem.

FULL DISCLOSURE: Yes, this is a LeetCode problem. I always like to research a solution before I give up and look at the solution. That's a better way to learn.

=======================================================================

[EDIT] :: A user suggested the below strategy, which worked. Posted in case it can help others...

public class countedInts implements Comparable<countedInts>{
    public int theInt, count;
    public countedInts(int a, int b) {
        this.theInt = a;
        this.count = b;
    }
    @Override
    public int compareTo(countedInts o) {
        return this.count - o.count;
    }
}


public int[] topKFrequent(int[] arr, int k) {

    // Edge cases
    if( arr == null ) {
        return null;
    }
    else if( arr.length == 0 ) {
        return arr;
    }
    
    int[] ret = new int[k];
    HashMap<Integer,Integer> myMap = new HashMap<>();
    PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    // Populate HashMap
    for( int i=0; i<arr.length; i   ) {
        if( !myMap.containsKey(arr[i]) ) {
            myMap.put(arr[i], 1);
        }
        else {
            myMap.put(arr[i], myMap.get(arr[i]) 1);
        }
    }

    // Transfer data into MaxHeap
    for( Map.Entry<Integer, Integer> glork : myMap.entrySet() ) {
        maxHeap.offer( new countedInts(glork.getKey(), glork.getValue()) );
    }

    // Pick out K-most values
    for( int i=0; i<k; i   ) {
        countedInts tmp = maxHeap.poll();
        ret[i] = tmp.theInt;
    }

    return ret;
}

CodePudding user response：

An approach using streams, which I think is somehow self documenting:

Stream over your array, group by identity and map to frequency using Collectors.counting, stream over the resulting map, sort entries by value in reverse order, limit the stream to k elements, and map to key

public int[] topKFrequent(int[] nums, int k) {
    return Arrays.stream(nums)
                 .boxed()
                 .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
                 .entrySet().stream()
                 .sorted(Map.Entry.<Integer, Long>comparingByValue().reversed())
                 .limit(k)
                 .map(Map.Entry::getKey)
                 .mapToInt(Integer::intValue)
                 .toArray();
}

CodePudding user response：

You can first use a HashMap to count the frequencies of all the numbers in the given array.

Then iterate through the hashmap to create the CountedInts objects and insert those objects into the priority queue.

CodePudding user response：

As described in the answer by @Haoliang, you can generate a Map containing a frequency of each number in the source array. And then populate a PriorityQueue with entries of this map.

This approach would more performant than sorting all the entries, especially when k is much lower than the number element in the array.

That is how the code might look like:

public static int[] topKFrequent(int[] nums, int k) {
    int[] result = new int[k];
    
    Map<Integer, Integer> freq = getFrequencies(nums);
    
    Queue<Map.Entry<Integer, Integer>> entries = populateQueue(freq);
    
    for (int i = 0; i < result.length; i  ) {
        result[i] = entries.remove().getKey();
    }
    return result;
}

Java 8 method merge() is used to make the code for generating the map frequencies more concise:

public static Map<Integer, Integer> getFrequencies(int[] arr) {
    Map<Integer, Integer> hist = new HashMap<>();
    for (int next: arr) {
        hist.merge(next, 1, Integer::sum);
    }
    return hist;
}

The method provided below creates a Max Heap using PriorityQueue and populates it with entries of the map:

public static Queue<Map.Entry<Integer, Integer>> populateQueue(Map<Integer, Integer> hist) {
    Queue<Map.Entry<Integer, Integer>> entries =
        new PriorityQueue<>(Map.Entry.<Integer, Integer>comparingByValue().reversed());

    entries.addAll(hist.entrySet());
    return entries;
}

main()

public static void main(String[] args) {
    int[] nums = {1, 1, 1, 2, 2, 3};
    System.out.println(Arrays.toString(topKFrequent(nums, 2)));
    
    nums = new int[]{1};
    System.out.println(Arrays.toString(topKFrequent(nums, 1)));
}

Output:

[1, 2]
[1]