Top K Frequent Elements Solutions in Java

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

import java.util.*;
import java.util.HashMap;
import javafx.util.Pair;

/// Using Tree Set
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution1 {

    private class PairComparator implements Comparator<Pair<Integer, Integer>>{

        @Override
        public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2){
            if(p1.getKey() != p2.getKey())
                return p2.getKey() - p1.getKey();
            return p1.getValue() - p2.getValue();
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {

        if(k <= 0)
            throw new IllegalArgumentException("k should be greater than 0");

        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for(int i = 0 ; i < nums.length ; i ++)
            if(freq.containsKey(nums[i]))
                freq.put(nums[i], freq.get(nums[i]) + 1);
            else
                freq.put(nums[i], 1);

        if(k > freq.size())
            throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");

        TreeSet<Pair<Integer, Integer>> set = new TreeSet<Pair<Integer, Integer>>(new PairComparator());
        for(Integer key: freq.keySet())
            set.add(new Pair(freq.get(key), key));

        ArrayList<Integer> res = new ArrayList<Integer>();
        for(Pair<Integer, Integer> p: set){
            res.add(p.getValue());
            if(res.size() == k)
                break;
        }

        return res;
    }

    private static void printList(List<Integer> nums){
        for(Integer num: nums)
            System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        printList((new Solution3()).topKFrequent(nums, k));
    }
}

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

import java.util.*;
import java.util.HashMap;
import javafx.util.Pair;
import java.util.Collections;

/// Sorting
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution2 {

    public List<Integer> topKFrequent(int[] nums, int k) {

        if(k <= 0)
            throw new IllegalArgumentException("k should be greater than 0");

        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for(int i = 0 ; i < nums.length ; i ++)
            if(freq.containsKey(nums[i]))
                freq.put(nums[i], freq.get(nums[i]) + 1);
            else
                freq.put(nums[i], 1);

        if(k > freq.size())
            throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");

        ArrayList<Integer> res = new ArrayList<Integer>();
        for(Integer key: freq.keySet())
            res.add(key);

        Collections.sort(res, (a, b) -> {
            if(freq.get(a) != freq.get(b))
                return freq.get(b) - freq.get(a);
            return a - b;
        });

        return res.subList(0, k);
    }

    private static void printList(List<Integer> nums){
        for(Integer num: nums)
            System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        printList((new Solution3()).topKFrequent(nums, k));
    }
}

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2017-11-17

import java.util.*;
import java.util.HashMap;

/// Priority Queue
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution3 {

    private class Pair implements Comparable<Pair>{
        public int num, freq;

        public Pair(int num, int freq){
            this.num = num;
            this.freq = freq;
        }

        @Override
        public int compareTo(Pair another){
            return this.freq - another.freq;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {

        if(k <= 0)
            throw new IllegalArgumentException("k should be greater than 0");

        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for(int i = 0 ; i < nums.length ; i ++)
            if(freq.containsKey(nums[i]))
                freq.put(nums[i], freq.get(nums[i]) + 1);
            else
                freq.put(nums[i], 1);

        if(k > freq.size())
            throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        for(Integer num: freq.keySet()){
            int numFreq = freq.get(num);
            if(pq.size() == k && numFreq > pq.peek().freq) pq.poll();
            if(pq.size() < k) pq.add(new Pair(num, numFreq));
        }

        ArrayList<Integer> res = new ArrayList<Integer>();
        while(!pq.isEmpty())
            res.add(pq.poll().num);

        return res;
    }

    private static void printList(List<Integer> nums){
        for(Integer num: nums)
            System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        printList((new Solution3()).topKFrequent(nums, k));
    }
}

/// Source : https://leetcode.com/problems/top-k-frequent-elements/description/
/// Author : liuyubobobo
/// Time   : 2020-03-14

import java.util.*;
import java.util.HashMap;
import java.util.HashSet;


/// Priority Queue contains n - k elements
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution4 {

    private class Pair implements Comparable<Pair>{
        public int num, freq;

        public Pair(int num, int freq){
            this.num = num;
            this.freq = freq;
        }

        @Override
        public int compareTo(Pair another){
            return another.freq - this.freq;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {

        if(k <= 0)
            throw new IllegalArgumentException("k should be greater than 0");

        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for(int i = 0 ; i < nums.length ; i ++)
            if(freq.containsKey(nums[i]))
                freq.put(nums[i], freq.get(nums[i]) + 1);
            else
                freq.put(nums[i], 1);

        if(k > freq.size())
            throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        for(Integer num: freq.keySet()){
            int numFreq = freq.get(num);
            if(freq.size() - k > 0 && pq.size() == freq.size() - k && numFreq < pq.peek().freq) pq.poll();
            if(freq.size() - k > 0 && pq.size() < freq.size() - k) pq.add(new Pair(num, numFreq));
        }

        HashSet<Integer> notContains = new HashSet<>();
        while(!pq.isEmpty())
            notContains.add(pq.poll().num);

        ArrayList<Integer> res = new ArrayList<Integer>();
        for(Integer key: freq.keySet())
            if(!notContains.contains(key)) res.add(key);

        return res;
    }

    private static void printList(List<Integer> nums){
        for(Integer num: nums)
            System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        printList((new Solution4()).topKFrequent(nums, k));
    }
}