返回数组中前 K 个高频元素_python前k个高频元素 给定一个非空的整数数组,返回其中出现频率前k高的元素。例如

题目

给定一个非空的整数数组，返回其中出现频率前 k 高的元素

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

输入: nums = [1], k = 1
输出: [1]

---

python解法：

return [num for num, _ in Counter(nums).most_common(k)]
1

java解法：

方法1

遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个【出现次数数组】，然后给这个【出现次数数组】排序，取前K个元素即为答案

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num: nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> list = new ArrayList<Integer>(map.keySet());
        list.sort((a1, a2) -> map.get(a2) - map.get(a1));
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度为$O(NlogN)$，N为数组中不同元素的个数，因为对数组进行排序需要这个时间复杂度
空间复杂度为$O(N)$，维护这个HashMap需要$O(N)$的空间

---

方法2

利用最小堆（小顶堆），每次向堆中插入元素时，若堆中的元素数目小于K，则直接插入，否则与堆顶比较，若次数小于堆顶，则插入堆中，插入的时间复制度为$O(logK)$，logK是将插入的元素放置在堆中合适位置所用的时间（需要沿着堆这个完全二叉树向下比较，直到找到大于它的值的节点）
因为Map一共有N个元素，因此可能需要进行N次插入，总的时间复杂度为$O(NlogK)$，要小于等于方法1的$O(NlogN)$

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num: nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(
                (arr1, arr2)->arr1[1] - arr2[1]);

        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            int num = entry.getKey(), count = entry.getValue();
            if(queue.size() == k){
                //与堆顶元素进行比较
                if(count > queue.peek()[1]){
                    queue.poll();  // 堆顶出堆
                    queue.offer(new int[]{num, count});  // 新元素进堆
                }
            }
            //堆内元素数目不足k，直接进堆
            else
                queue.offer(new int[]{num, count});
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll()[0];
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

方法3

快速排序，思路很清晰，快速排序的过程中，就是选定一个元素，元素左边的元素都大于它，元素右边的元素都小于它，如果左边的元素数目大于k，则不需要对右边元素进行排序，否则假设左边元素数目为x,然后只需要对右边元素进行排序，取前(k-x-1)个元素即可，不管是哪种情况，只需要对某一边进行排序，而不需要对两边都排序
即平均情况下每次只需要对当前数组的一半进行排序（在一般的快速排序中，每次都需要对N个元素进行排序），一共排序的次数为logN：

n+n/2+n/4+…+1 = n(1+1/2+1/4+…+1/(2^m))< n(1+1/2+1/4+…+无穷小）= 2n (其中2^(m-1) < n <2^(m+1))，因此进行快速排序算法的时间复杂度为$O(N)$，算法的平均时间复杂度为$O(N)$，最坏的时间复杂度为$O(N^2)$

另外，$O(N)$的时间复杂度推导也可以根据主定理：设时间复杂度为f(N)，则$f(N)=O(N)+f(\frac{N}{2})$可以推出$f(N)=O(N)$

空间复杂度为$O(N)$

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        List<int[]> values = new ArrayList<int[]>();
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            values.add(new int[]{num, count});
        }
        int[] ret = new int[k];
        qsort(values, 0, values.size() - 1, ret, 0, k);
        return ret;
    }

    public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
        int picked = (int) (Math.random() * (end - start + 1)) + start;
        Collections.swap(values, picked, start);
        
        int pivot = values.get(start)[1];
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            if (values.get(i)[1] >= pivot) {
                Collections.swap(values, index + 1, i);
                index++;
            }
        }
        Collections.swap(values, start, index);

        if (k <= index - start) {
            qsort(values, start, index - 1, ret, retIndex, k);
        } else {
            for (int i = start; i <= index; i++) {
                ret[retIndex++] = values.get(i)[0];
            }
            if (k > index - start + 1) {
                qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
            }
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

本文参考：leetcode官方解答