【LeetCode】 347. 前 K 个高频元素桶排序最小堆

小咪咪 2021-06-10 20:38 270阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

1.  首先还是要考虑，数组遍历不完没有结果，所以，遍历第一遍，使用hashmap记录不同数字出现的次数
2.  第二次遍历hashmap，以出现的次数作为key，存入到数组中
3.  第三次，倒序遍历数组，打印存储的数字即可

### 代码 ###

class Solution { 
        public List<Integer> topKFrequent(int[] nums, int k) { 
            int len = nums.length;
            // 遍历数组找到每个元素出现的频率
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < len; i++) { 
                int num = nums[i];
                if (map.containsKey(num)) { 
                    map.put(num, map.get(num) + 1);
                } else { 
                    map.put(num, 1);
                }
            }
            // 添加到每个元素出现的频率的List中
            List<Integer>[] lists = new List[len + 1];
            for (int num : map.keySet()) { 
                int count = map.get(num);
                if (lists[count] == null) { 
                    lists[count] = new ArrayList() { { 
                        add(num);
                    }};
                } else { 
                    lists[count].add(num);
                }
            }
            // 倒序遍历桶，拿到元素
            List<Integer> res = new ArrayList<>();
            int i = len;
            while (k > 0 && i > 0) { 
                if (lists[i] != null) { 
                    for (int num : lists[i]) { 
                        res.add(num);
                        k--;
                    }
                }
                i--;
            }
            return res;
        }
    }

### 使用堆排序 ###

1.  首先还是记录出现的次数
2.  根据出现的次数建立最小堆
3.  从堆中拿元素即可

class Solution { 
        public List<Integer> topKFrequent(int[] nums, int k) { 
            // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
            HashMap<Integer,Integer> map = new HashMap();
            for(int num : nums){ 
                if (map.containsKey(num)) { 
                   map.put(num, map.get(num) + 1);
                 } else { 
                    map.put(num, 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> res = new ArrayList<>();
            while (!pq.isEmpty()) { 
                res.add(pq.remove());
            }
            return res;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/top-k-frequent-elements/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/360934e3ff2d483db1c46a32624bb23c.png