当前位置:   article > 正文

[LeetCode]347. 前 K 个高频元素_347. 前k个高频元素

347. 前k个高频元素

题目

347.K 个高频元素
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:

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

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

提示:

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
 

进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

方法1:HashMap+桶排

public int[] topKFrequent(int[] nums, int k) {
    //k:nums的每一个数,v:nums中每一个数出现的次数
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int x : nums) {
        freqMap.put(x, freqMap.getOrDefault(x, 0) + 1);
    }
    //bucket[freq]出现的次数,哪些数出现了freq次
    List<Integer>[] bucket = new List[nums.length + 1];
    for (int x : freqMap.keySet()) {
        int freq = freqMap.get(x);
        if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
        bucket[freq].add(x);
    }
    List<Integer> res = new ArrayList<>();
    //从高到低freq开始收集res
    for (int i = bucket.length - 1; i >= 0; --i) {
        if (bucket[i] != null) {
            for (int j = 0; j < bucket[i].size() && res.size() < k; j++) {
                res.add(bucket[i].get(j));
            }
        }
    }
    int[] ans = new int[res.size()];
    for (int i = 0; i < res.size(); i++) ans[i] = res.get(i);
    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

方法2:HashMap+大根堆

 public int[] topKFrequent(int[] nums, int k) {
            //k:nums的每一个数,v:nums中每一个数出现的次数
            Map<Integer, Integer> freqMap = new HashMap<>();
            for (int x : nums) {
                freqMap.put(x, freqMap.getOrDefault(x, 0) + 1);
            }
            //做一个大根堆
            PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
            for (Map.Entry<Integer, Integer> e : freqMap.entrySet()) {
                pq.offer(e);
            }
            List<Integer> res = new ArrayList<>();
            while (res.size() < k) {
                res.add(pq.poll().getKey());
            }
            int[] ans = new int[res.size()];
            for (int i = 0; i < res.size(); i++) ans[i] = res.get(i);
            return ans;
        }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

方法3:HashMap+TreeMap

        public int[] topKFrequent(int[] nums, int k) {
            //k:nums的每一个数,v:nums中每一个数出现的次数
            Map<Integer, Integer> freqMap = new HashMap<>();
            for (int x : nums) {
                freqMap.put(x, freqMap.getOrDefault(x, 0) + 1);
            }
            TreeMap<Integer, List<Integer>> treeMap = new TreeMap<>();
            for (int x : freqMap.keySet()) {
                int freq = freqMap.get(x);
                treeMap.putIfAbsent(freq, new ArrayList<>());
                treeMap.get(freq).add(x);
            }
            List<Integer> res = new ArrayList<>();
            while (res.size() < k) {
                Map.Entry<Integer, List<Integer>> e = treeMap.pollLastEntry();
                res.addAll(e.getValue());
            }
            int[] ans = new int[res.size()];
            for (int i = 0; i < res.size(); i++) ans[i] = res.get(i);
            return ans;
        }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

方法4:快速排序

public int[] topKFrequent(int[] nums, int k) {
    //k: 元素num v:出现的频次
    Map<Integer, Integer> map = new HashMap<>();
    for (int x : nums) map.put(x, map.getOrDefault(x, 0) + 1);
    List<int[]> freqList = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : map.entrySet()) {
        int num = e.getKey(), freq = e.getValue();
        freqList.add(new int[]{num, freq});
    }
    int[] res = new int[k];
    quickSort(freqList, 0, freqList.size() - 1, res, 0, k);
    return res;

}

/**
 * @param freqList 频次的list [0]为num [1]为freq
 * @param start    list的开始位置
 * @param end      list的结束位置
 * @param res      结果数组
 * @param resIndex 结果数组的当前待添加的下标索引
 * @param k        k
 */
private void quickSort(List<int[]> freqList, int start, int end,
                       int[] res, int resIndex, int k) {
    int pivotIndex = (int) (Math.random() * (end - start + 1)) + start;//随机选择哨兵
    Collections.swap(freqList, start, pivotIndex);//交换哨兵与start的位置
    int pivotFreq = freqList.get(start)[1];//当前的频次
    int index = start;
    for (int i = start + 1; i <= end; i++) {
        if (freqList.get(i)[1] >= pivotFreq) {//将频次高的放在左侧,频次低的放在右侧
            Collections.swap(freqList, index + 1, i);
            index++;
        }
    }
    Collections.swap(freqList, start, index);//将哨兵的位置放置在正确的位置
    if (index - start >= k) {//[start...index]段的元素比k多,需要在[start...index]段继续缩小范围
        quickSort(freqList, start, index - 1, res, resIndex, k);
    } else {
        for (int i = start; i <= index; i++) {//左侧部分即[start...index]都是需要的,开始收集
            res[resIndex++] = freqList.get(i)[0];
        }
        if (index - start + 1 < k) { // 当pivot和起点间的个数小于k时,则从pivot到end再继续找剩下的前(k - (pivot - start + 1))大的元素
            quickSort(freqList, index + 1, end, res, resIndex, 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
  • 46
  • 47
  • 48
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/685331
推荐阅读
相关标签
  

闽ICP备14008679号