LeetCode347-前K个高频元素

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/top-k-frequent-elements/

中文链接：https://leetcode-cn.com/problems/top-k-frequent-elements/

题目详述

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

示例 1:

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

示例 2:

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

说明：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

题目详解

TopK 问题。

因为是求出现频率前 k 高的元素，而不是求前K大的元素，所以首先要统计每个元素的出现次数，构造一个从数据到出现次数的映射，据此来进行比较。

方法一：利用桶排序，时间复杂度为 O(n)。

  • 把元素出现次数作为桶的下标，元素作为桶的数据。
  • 从后往前遍历桶，就是从频率高到频率低进行遍历，可以得到 TopK。
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class LeetCode_00215 {

    public int findKthLargest(int[] nums, int k) {
        // 转换为数组从小到大排序后的下标
        k = nums.length - k;
        return quickSelect(nums, k);
    }

    /**
     * 选择第 k 小的元素（从 0 开始计数），使 a[k] 在数组排序后正确的位置上
     * @param nums  数组 nums
     * @param k     第 k 小
     * @return      nums[k]
     */
    private int quickSelect(int[] nums, int k) {
        int lo = 0;
        int hi = nums.length - 1;
        // 逐步缩小 [lo, hi] 的范围
        while (lo < hi) {
            int i = partition(nums, lo, hi);
            if (i < k) {
                lo = i + 1;
            } else if (i > k) {
                hi = i - 1;
            } else {
                return nums[i];
            }
        }
        // 此时 lo = hi = k
        return nums[lo];
    }

    /**
     * 分割方法，获得切分下标
     * @param nums     待分割数组
     * @param lo    待分割数组的开始下标
     * @param hi    待分割数组的结束下标
     * @return      切分下标
     */
    private int partition(int[] nums, int lo, int hi) {
        // 将三者的中位数放在数组头部，再来分割，即把三者的中位数作为 pivot
        int m = median3(nums, lo, lo + (hi - lo) / 2, hi);
        swap(nums, lo, m);
        int i = lo;
        int j = hi + 1;
        int v = nums[lo];
        while (true) {
            // 从左往右找到第一个大于 pivot 的位置
            while (nums[++i] < v && i < hi) {}
            // 从右往左找到第一个小于 pivot 的位置
            while (nums[--j] > v) {}
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, lo, j);
        return j;
    }

    /**
     * 得到 nums[i], nums[j], nums[k] 的中位数的下标
     * @param nums  数组
     * @param i     下标 i
     * @param j     下标 j
     * @param k     下标 k
     * @return      中位数的下标
     */
    private static int median3(int[] nums, int i, int j, int k) {
        return nums[i] < nums[j] ?
                (nums[j] < nums[k] ? j : nums[i] < nums[k] ? k : i) :
                (nums[k] < nums[j] ? j : nums[k] < nums[i] ? k : i);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

方法二：利用小根堆，时间复杂度为 O(nlog(k))。

  • 根据元素出现次数构造小根堆。
  • 遍历原数组，不断向小根堆添加元素，当小根堆大小超过 k 时，弹出队顶（最小值），即维持小根堆的大小最大为 k。
  • 遍历结束后，小根堆里的元素为 TopK。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00347 {
    
    // 时间复杂度 O(nlog(k))
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 构造一个从整数到出现次数的映射
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 构造一个小根堆，根据出现次数排序
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(map::get));
        for (Integer num : map.keySet()) {
            heap.add(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        // 转为 List
        return new ArrayList<>(heap);
    }
}