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

冷不防 2022-04-15 03:20 184阅读 0赞

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

**相关文章：**

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

--------------------

**文章目录：**

题目描述:

java实现方法1：

Python实现1：

java实现方法2：

python实现方法2：

java实现方法3：

python实现方法3：

源码地址：

--------------------

### 题目描述: ###

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

**示例 1:**

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

**示例 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;
        }

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

空间复杂度：O(n)

--------------------

### Python实现方法1： ###

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： ###

/**
         * @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： ###

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;
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方法3： ###

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][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode