找出一个数组中的前k个高频元素

113 阅读 0 评论 75 点赞

我是靠谱客的博主辛勤电脑，这篇文章主要介绍找出一个数组中的前k个高频元素，现在分享给大家，希望可以做个参考。

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

例如，

给定数组 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。

注意：

你可以假设给定的 k 总是合理的，1 ≤ k ≤ 数组中不相同的元素的个数。

第一步基本都是一致的,需要统计出每个元素的出现次数 : 先遍历一遍数组,以数组的值做key存放到map中,初始value为1,当有相同的key时,把value加1,然后map中的value就是每个元素的出现次数了.
方式1:简单暴力一点 , 然后对map中的value进行一次全排序,然后输出前k个高频的元素即可.

方式2:采用最小堆优化一下 , 构建一个容量为k的最小堆 , 遍历map中的value ,堆的数量小于k时添加 , 等于k之后,用新的value与堆中的最小值进行PK, 大于堆中的最小值就添加进堆,不大于就丢弃 , 遍历完map之后,输出堆中的元素就是前k大的元素了.

方式3:采用桶排序 , 构建n+1个桶, 每个桶里放一个数组 , (为什么是数组?因为可能2出现了5次,3也出现了5次,所以5这个桶需要用数组盛放) ,然后把value对应的key填入对应的桶中 , 前k个高频元素就从桶的结束位置倒叙遍历k个元素即可. 桶排序就是典型的空间换时间.

方式4:借用了快速排序的思想,我们要找出前k个元素,构建一个从大到小的数组, 在排序的过程中,如果能找到一个基准值,前面的都比基准值大,这个基准值又是k,那么就说明,前面的数据就是前k个高频元素了.

全排序法:

复制代码

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
 public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计元素的频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        // 对元素按照频率进行降序排序
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(freqMap.entrySet());
        Collections.sort(list, 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();
            }
        });
        
        // 取出前k个元素
        int count = 0;
        List<Integer> ret = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : list) {
            ret.add(entry.getKey());
            ++count;
            if (count >= k) {
                break;
            }
        }
        return ret;
    }

最小堆法:

复制代码

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
 public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计元素的频率
        Map<Integer, Integer> map = new HashMap<>(16);
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });

        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }

        // 取出最小堆中的元素
        List<Integer> ret = new ArrayList<>();
        while (!pq.isEmpty()) {
            ret.add(pq.remove());
        }

        return ret;
    }

桶排序法

复制代码

public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计元素的频次
        Map<Integer, Integer> int2FreqMap = new HashMap<>(16);
        for (int num : nums) {
            int2FreqMap.put(num, int2FreqMap.getOrDefault(num, 0) + 1);
        }
        
        // 桶排序
        List<Integer>[] bucket = new List[nums.length + 1];
        for (Integer key : int2FreqMap.keySet()) {
            int freq = int2FreqMap.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
        
        // 逆序（频次由高到低）取出元素
        List<Integer> ret = new ArrayList<>();
        for (int i = nums.length; i >= 0 && ret.size() < k; --i) {
            if (bucket[i] != null) {
                for (Integer key : bucket[i]) {
                    if (ret.size()<k){
                        ret.add(key);
                    }else {
                        return ret;
                    }
                }
            }
        }
        
        return ret;
    }

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
 public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计元素的频次
        Map<Integer, Integer> int2FreqMap = new HashMap<>(16);
        for (int num : nums) {
            int2FreqMap.put(num, int2FreqMap.getOrDefault(num, 0) + 1);
        }
        
        // 桶排序
        List<Integer>[] bucket = new List[nums.length + 1];
        for (Integer key : int2FreqMap.keySet()) {
            int freq = int2FreqMap.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
        
        // 逆序（频次由高到低）取出元素
        List<Integer> ret = new ArrayList<>();
        for (int i = nums.length; i >= 0 && ret.size() < k; --i) {
            if (bucket[i] != null) {
                for (Integer key : bucket[i]) {
                    if (ret.size()<k){
                        ret.add(key);
                    }else {
                        return ret;
                    }
                }
            }
        }
        
        return ret;
    }