package LeetCode;

import javafx.util.Pair;

import java.util.*;

public class LeetCode347 {


    // 347. Top K Frequent Elements
    // https://leetcode.com/problems/top-k-frequent-elements/description/
    // : O(nlogk)
    // : O(n + k)

    private class PairComparator implements Comparator {

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


    // nums = [1,1,1,2,2,3], k = 2
    public    List topKFrequent(int[] nums, int k) {

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

        // freq,k
        // ,, (,) 

        // 
        PriorityQueue pq = new PriorityQueue(new PairComparator());
        for(Integer num: freq.keySet()){
            int numFreq = freq.get(num);

            // k
            if(pq.size() == k){
                if(numFreq > pq.peek().getKey()){
                    pq.poll();
                    pq.add(new Pair(numFreq, num));
                }
            } else
                pq.add(new Pair(numFreq, num));

        }

        ArrayList res = new ArrayList();
        while(!pq.isEmpty())
            res.add(pq.poll().getValue());

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};


        new LeetCode347().topKFrequent(nums, 2);


    }


}