leetcode/出现频率最高的k个数字，频率前k高的数字

package com.xcrj;

import java.util.*;


public class Solution60 {
    
    public int[] topKFrequent1(int[] nums, int k) {
        Map map = new HashMap<>();
        // 统计每个元素出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 优先队列按照次数从小到大排序
        Queue queue = new PriorityQueue(new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for (Map.Entry entry : map.entrySet()) {
            int v = entry.getKey();
            int c = entry.getValue();
            // 优先队列中有k个元素了
            if (queue.size() == k) {
                // 放入出现次数更大的元素：对头次数小于当前元素出现次数，出队对头元素
                if (queue.peek()[1] < c) {
                    queue.poll();
                    queue.offer(new int[]{v, c});
                }
            }
            // 队列不满k个元素，直接添加到队列中
            else {
                queue.offer(new int[]{v, c});
            }
        }

        // 将队列中的值转储到数组
        // k：出现频率最高的k个数字
        int[] rs = new int[k];
        int i = 0;
        while (!queue.isEmpty()) {
            rs[i++] = queue.poll()[0];
        }

        return rs;
    }

    
    public int[] topKFrequent2(int[] nums, int k) {
        // 统计每个元素出现次数
        Map map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 构建快速排序所需链表
        List list = new ArrayList<>();
        for (Map.Entry entry : map.entrySet()) {
            list.add(new int[]{entry.getKey(), entry.getValue()});
        }

        // 快速排序
        int[] rs = new int[k];
        quickSort(list, 0, list.size() - 1, k, rs, 0);
        return rs;
    }

    
    public void quickSort(List list, int start, int end, int k, int[] rs, int ri) {
        
        // 从序列中随机选择一个索引点的中 放到开头做轴值
        int picked = (int) (Math.random() * (end - start + 1)) + start;
        // 交换索引指向元素，索引值没变，start和picked没变
        Collections.swap(list, picked, start);

        // 寻找比轴值大或等的值依次放到轴后面
        int pivot = list.get(start)[1];
        int j = start;
        // =end，end=list.size() - 1
        for (int i = start + 1; i <= end; i++) {
            // 始终和开始值比较
            if (list.get(i)[1] >= pivot) {
                Collections.swap(list, j + 1, i);
                j++;
            }
        }

        // start指向pivot<=[start,j)的值，把小的值放后面
        Collections.swap(list, start, j);

        // [start,j]多于k个元素，快速排序[start,j-1]的序列
        if (k <= j - start) {
            quickSort(list, start, j - 1, k, rs, ri);
        }
        // [start,j]少于k个元素
        else {
            // 找到了前m多的元素，m
                rs[ri++] = list.get(i)[0];
            }
            // 在[j+1,end]的序列中寻找剩下的k-m多的值
            if (k > j - start + 1) {
                quickSort(list, j + 1, end, k - (j - start + 1), rs, ri);
            }
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/g5c51o/solution/chu-xian-pin-lu-zui-gao-de-k-ge-shu-zi-b-a1td/
来源：力扣（LeetCode）