347. 前 K 个高频元素

347. 前 K 个高频元素

public class topK {
//// 第一种方法，需要对所有的数据进行排序 时间复杂度n*logn
//    public static int[] topKFrequent(int[] nums, int k) {
//        HashMap<Integer, Integer> hashMap = new HashMap<>();
//
//        for (int i = 0; i < nums.length; i++) {
//            hashMap.put(nums[i],hashMap.getOrDefault(nums[i],0)+1);
//        }
//
//        Set<Map.Entry<Integer, Integer>> entries = hashMap.entrySet();
//        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(entries);
//
//        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
//            @Override
//            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//                return o2.getValue()-o1.getValue();
//            }
//        });
//
//        int[] result = new int[k];
//        for (int i = 0; i < k; i++) {
//            result[i] = list.get(i).getKey();
//        }
//        return result;
//    }

    // 维护一个长度为k优先队列，每次只排序k个数  时间复杂度是n*logk
    // 小顶堆实现，过程是每次加进来一个新值，和当前K个值做比较，把最小的运送到堆顶，并弹出。（主要求前K大的数要把大的留下，
    // 小的弹走，留下的就是topK）
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i],hashMap.getOrDefault(nums[i],0)+1);
        }

        // 后元素减前面
        Comparator<Map.Entry<Integer, Integer>> comparator = new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        };


        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(comparator);

        for(Map.Entry<Integer, Integer> entry:hashMap.entrySet()){
            queue.add(entry);
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll().getKey();
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        int[] frequent = topKFrequent(nums, k);
        for (int i = 0; i < frequent.length; i++) {
            System.out.println(frequent[i]);
        }
    }

}

参考:https://www.bilibili.com/video/BV1Xg41167Lz/?spm_id_from=333.337.search-card.all.click&vd_source=46d50b5d646b50dcb2a208d3946b1598