347前K個高頻元素 https://leetcode-cn.com/problems/top-k-frequent-elements/
1、題目描述給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
提示：
你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。你的算法的時間複雜度必須優於 O(n log n) , n 是數組的大小。題目數據保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的。2、思路都需要通過一個map統計各個數字出現的頻率，區別在如何對統計的map數據進行處理獲取前topk個元素
思路1：通過把map的key，value封裝對象，通過優先級隊列維護一個K個大小的最小堆。時間複雜度O(nlogk)，空間複雜度N
思路2：在統計數字出現個數時，同時計算出，最大頻率max,然後按照頻率構建桶排序數組，遍歷數組即可獲得結果。時間複雜度N，空間複雜度 N(可能存在max很大而申請的數組浪費空間)
思路3：使用treemap，頻率為key，value為當前頻率下的元素。依次獲取treemap的尾部元素直到夠K個即可。
3、題解思路1
//思路1：先通過map統計各個數字出現的頻率，然後通過優先級隊列列構建小頂堆，取最大的topk
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
int[] res = {};
return res;
}
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int key = nums[i];
if (map.containsKey(key)) {
map.put(key,map.get(key) + 1);
} else {
map.put(key, 1);
}
}
//使用優先級隊列構建小頂堆，取最大的topk
PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>(){
public int compare(Pair p1,Pair p2) {
return p1.count - p2.count;
}
});
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
Pair pair = new Pair(entry.getKey(),entry.getValue());
queue.offer(pair);
if (queue.size() > k) {
queue.poll();
}
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = queue.poll().key;
}
return res;
}
class Pair{
int key;
int count;
public Pair(int key,int count) {
this.key = key;
this.count = count;
}
}
}
//優化上面的代碼，優先級隊列直接存儲Map.Entry，按照統計個數進行構建最小堆
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
int[] res = {};
return res;
}
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int key = nums[i];
if (map.containsKey(key)) {
map.put(key,map.get(key) + 1);
} else {
map.put(key, 1);
}
}
//使用優先級隊列構建小頂堆，取最大的topk
PriorityQueue<Map.Entry<Integer,Integer>> queue =
new PriorityQueue<Map.Entry<Integer,Integer>>(
new Comparator<Map.Entry<Integer,Integer>>(){
public int compare(Map.Entry<Integer,Integer> entry1,Map.Entry<Integer,Integer> entry2) {
return entry1.getValue() - entry2.getValue();
}
});
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
queue.offer(entry);
if (queue.size() > k) {
queue.poll();
}
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = queue.poll().getKey();
}
return res;
}
}思路2
//思路2：藉助於桶排序找k個最大數
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] res = new int[k];
//1、統計每個數字出現的個數
Map<Integer,Integer> map = new HashMap<>();
int max = 0;
for (int i = 0;i < nums.length;i++) {
map.put(nums[i], map.get(nums[i]) != null ? map.get(nums[i]) + 1 : 1);
//出現頻率最大的個數
max = Math.max(max, map.get(nums[i]));
}
//2、構建一個桶，通過各個出現相同頻率的放在一個桶中（出現的頻率分桶）
List<Integer>[] dp = new List[max + 1];
for (Integer i : map.keySet()) {
int frequent = map.get(i);
if (dp[frequent] == null) dp[frequent] = new ArrayList<>();
dp[frequent].add(i);
}
int p = 0;
//3、逆序遍歷桶，找夠K個數
for (int i = dp.length - 1;i >= 0 && p < k;i--) {
List<Integer> temp = dp[i];
if (temp != null) {
for (Integer j : temp) {
if (p == k) return res;
res[p++] = j;
}
}
}
return res;
}
}思路3
//思路3：藉助於treemap找k個最大數
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
int[] res = {};
return res;
}
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
}
TreeMap<Integer,List<Integer>> treemap = new TreeMap<>();
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
if (!treemap.containsKey(entry.getValue())) {
treemap.put(entry.getValue(),new LinkedList<Integer>());
}
treemap.get(entry.getValue()).add(entry.getKey());
}
int[] res = new int[k];
int i = 0;
while (i < k) {
Map.Entry<Integer,List<Integer>> entry = treemap.pollLastEntry();
for (int j = 0; j < entry.getValue().size(); j++) {
res[i++] = entry.getValue().get(j);
}
}
return res;
}
}