LeetCode:347. Top K Frequent Elements(找出出现频率最高的K个数)

115 阅读 0 评论 76 点赞

我是靠谱客的博主微笑乌冬面，这篇文章主要介绍LeetCode:347. Top K Frequent Elements(找出出现频率最高的K个数)，现在分享给大家，希望可以做个参考。

文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

相关文章：

LeetCode：55. Jump Game（跳远比赛）
Leetcode：300. Longest Increasing Subsequence（最大增长序列）
LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）

文章目录：

题目描述:

java实现方法1：

Python实现1：

java实现方法2：

python实现方法2：

java实现方法3：

python实现方法3：

源码地址：

题目描述:

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

示例 1:

复制代码

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

示例 2:

复制代码

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

java实现方法1：

复制代码

/**
     * @param nums 数组
     * @param k    前面k数
     * @return 链表
     */
    public int[] topKFrequent(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[]{};
        }
        HashMap<Integer, Integer> frequentMap = getFrequentMap(nums);
        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>(k, (e1, e2) -> (e1.getValue() - e2.getValue()));
        for (Map.Entry<Integer, Integer> entry : frequentMap.entrySet()) {
            if (maxHeap.size() < k) {
                maxHeap.offer(entry);
            } else if (entry.getValue() > maxHeap.peek().getValue()) {
                maxHeap.poll();
                maxHeap.offer(entry);
            }
        }
        return maxHeap.stream().mapToInt(e -> e.getKey().intValue()).toArray();
    }
    /**
     * 转换成频率map
     *
     * @param nums 数组
     * @return map
     */
    private HashMap<Integer, Integer> getFrequentMap(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return map;
    }

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
   /**
     * @param nums 数组
     * @param k    前面k数
     * @return 链表
     */
    public int[] topKFrequent(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[]{};
        }
        HashMap<Integer, Integer> frequentMap = getFrequentMap(nums);
        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>(k, (e1, e2) -> (e1.getValue() - e2.getValue()));
        for (Map.Entry<Integer, Integer> entry : frequentMap.entrySet()) {
            if (maxHeap.size() < k) {
                maxHeap.offer(entry);
            } else if (entry.getValue() > maxHeap.peek().getValue()) {
                maxHeap.poll();
                maxHeap.offer(entry);
            }
        }
        return maxHeap.stream().mapToInt(e -> e.getKey().intValue()).toArray();
    }
    /**
     * 转换成频率map
     *
     * @param nums 数组
     * @return map
     */
    private HashMap<Integer, Integer> getFrequentMap(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return map;
    }

时间复杂度：O(log(n).n)

空间复杂度：O(n)

Python实现方法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
    def top_k_frequent_2(self, nums: List[int], k: int) -> List[int]:
        '''
            截取链表长度
        Args:
            nums: 数组
            k: 最大k
        Returns:
            频率最高的k
        '''
        result = []
        num_map = self.get_num_map(nums)
        q = queue.PriorityQueue()
        for e in num_map.items():
            q.put([e[1], e[0]])
            if q.qsize() > k:
                q.get()

        while not q.empty():
            result.append(q.get()[1])
        return result
   

   def get_num_map(self, nums: List[int]) -> dict:
        '''
            生成频率数组
        Args:
            nums:数组
        Returns:
            返回map
        '''
        num_map = {}
        for num in nums:
            if num in num_map:
                num_map[num] += 1
            else:
                num_map[num] = 1
        return num_map

时间复杂度：O(log(n).n)

空间复杂度：O(n)

java实现方法2：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   /**
     * @param nums 数组
     * @param k    前面k数
     * @return 链表
     */
    public int[] topKFrequent2(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[]{};
        }
        HashMap<Integer, Integer> frequentMap = new HashMap<>();
        for (int num : nums) {
            frequentMap.put(num, frequentMap.getOrDefault(num, 0) + 1);
        }
        return frequentMap.entrySet().stream().sorted((e1, e2) -> (e2.getValue() - e1.getValue()))
                .limit(k).mapToInt(e -> e.getKey()).toArray();
    }

时间复杂度：O(n.log(n))

空间复杂度：O(n)

python实现方法2：

复制代码

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
    def get_num_map(self, nums: List[int]) -> dict:
        '''
            生成频率数组
        Args:
            nums:数组
        Returns:
            返回map
        '''
        num_map = {}
        for num in nums:
            if num in num_map:
                num_map[num] += 1
            else:
                num_map[num] = 1
        return num_map

    def top_k_frequent(self, nums: List[int], k: int) -> List[int]:
        '''
            截取链表长度
        Args:
            nums: 数组
            k: 最大k
        Returns:
            频率最高的k
        '''
        num_map = self.get_num_map(nums)
        dict_sort_list = sorted(num_map.items(), key=lambda x: x[1], reverse=True)
        return [x[0] for x in dict_sort_list[0:k]]

时间复杂度：O(n.log(n))

空间复杂度：O(n)

java实现方法3：

复制代码

/**
     * @param nums 数组
     * @param k    前面k数
     * @return 链表
     */
    public int[] topKFrequent3(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[]{};
        }
        // 计算出现次数
        HashMap<Integer, Integer> frequentMap = new HashMap<>();
        for (int num : nums) {
            frequentMap.put(num, frequentMap.getOrDefault(num, 0) + 1);
        }
        // 获取数字出现的最大次数
        int maxSize = 0;
        for (Map.Entry<Integer, Integer> entry : frequentMap.entrySet()) {
            if (entry.getValue() > maxSize) {
                maxSize = entry.getValue();
            }
        }
        // 找到出现次数最多的数组
        int[] result = new int[k];
        while (k > 0) {
            for (Map.Entry<Integer, Integer> entry : frequentMap.entrySet()) {
                if (entry.getValue() == maxSize) {
                    result[k - 1] = entry.getKey();
                    k--;
                }
            }
            maxSize--;
        }
        return result;
    }

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
   /**
     * @param nums 数组
     * @param k    前面k数
     * @return 链表
     */
    public int[] topKFrequent3(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[]{};
        }
        // 计算出现次数
        HashMap<Integer, Integer> frequentMap = new HashMap<>();
        for (int num : nums) {
            frequentMap.put(num, frequentMap.getOrDefault(num, 0) + 1);
        }
        // 获取数字出现的最大次数
        int maxSize = 0;
        for (Map.Entry<Integer, Integer> entry : frequentMap.entrySet()) {
            if (entry.getValue() > maxSize) {
                maxSize = entry.getValue();
            }
        }
        // 找到出现次数最多的数组
        int[] result = new int[k];
        while (k > 0) {
            for (Map.Entry<Integer, Integer> entry : frequentMap.entrySet()) {
                if (entry.getValue() == maxSize) {
                    result[k - 1] = entry.getKey();
                    k--;
                }
            }
            maxSize--;
        }
        return result;
    }

时间复杂度：O(n)

空间复杂度：O(n)

python实现方法3：

复制代码

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
    def top_k_frequent_3(self, nums: List[int], k: int) -> List[int]:
        '''
           截取链表长度
       Args:
           nums: 数组
           k: 最大k
       Returns:
           频率最高的k
       '''
        num_map = self.get_num_map(nums)
        # 找到最大出现次数
        max_size = 0
        for num in num_map:
            if num_map[num] > max_size:
                max_size = num_map[num]
        # 找结果集
        result = []
        while k > 0:
            for num in num_map:
                if num_map[num] == max_size:
                    result.append(num)
                    k -= 1
            max_size -= 1
        return result

时间复杂度：O(n)

空间复杂度：O(n)

源码地址：

https://github.com/zhangyu345293721/leetcode

最后

以上就是微笑乌冬面最近收集整理的关于LeetCode:347. Top K Frequent Elements(找出出现频率最高的K个数)的全部内容，更多相关LeetCode:347.内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：LeetCode
浏览次数：115 次浏览
发布日期：2023-08-27 08:05:24
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzo_14_fx_12__7__22_3.html

LeetCode:347. Top K Frequent Elements(找出出现频率最高的K个数)

题目描述:

java实现方法1：

Python实现方法1：

java实现方法2：

python实现方法2：

java实现方法3：

python实现方法3：

源码地址：

最后

评论列表共有 0 条评论

发表评论取消回复

LeetCode:347. Top K Frequent Elements(找出出现频率最高的K个数)

题目描述:

java实现方法1：

Python实现方法1：

java实现方法2：

python实现方法2：

java实现方法3：

python实现方法3：

源码地址：

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复