作者Rushia (みけねこ的鼻屎)
看板Marginalman
標題Re: [閒聊] 每日LeetCode
時間Tue May 23 01:42:25 2023
https://leetcode.com/problems/top-k-frequent-elements/description/
347. Top K Frequent Elements
給你一個陣列 nums，找出出現次數最多次的前k個元素是哪些。
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
思路
1.先用一個Map統計所有元素的出現次數。
2.把所有元素丟進一個最大堆積。
3.從最大堆積中取出k個元素就是答案了。
Java Code：
------------------------------------------
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) ->
map.get(b) - map.get(a));
queue.addAll(map.keySet());
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = queue.poll();
}
return res;
}
}
------------------------------------------
明天七點四十要起床 每日睡眠時間--
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1684777349.A.BEE.html
推 PyTorch: 大師 05/23 01:43
推 a9486l: 大師 05/23 01:43
推 SiranuiFlare: 大師 05/23 01:46
→ dannyko: 大師 05/23 04:37
推 ekids1234: 這題想做 space O(1) 的話應該要用二分搜或是 05/27 22:50
→ ekids1234: quick select. 05/27 22:50
→ ekids1234: 二分搜的想法是去猜那個 res 的頻率到底多少 05/27 22:50
→ ekids1234: 不對 這兩者好像都還是得 O(n) = = 05/27 22:52
推 ekids1234: 想了想用 pq 的話真是簡單又易解，狗才寫二分搜 QQQ 05/27 23:03
→ ekids1234: 不過二分搜的優點是 logn*k, k是distinct freq 數量 05/27 23:07