package sy181215;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
/**
* @author suyuan
*
给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。
*/
public class leetcode_347前K个高频元素
{
public static void main(String[] args)
{
//[1,1,1,2,2,3]
// int [] nums=new int[]{1,1,1,2,2,3,5,4,5,5,8,3};
int [] nums=new int[]{1,1,1,2,2,3};
System.out.println(topKFrequent(nums, 2));
}
public static List<Integer> topKFrequent(int[] nums, int k)
{
Map<Integer, Integer> map=new HashMap<Integer, Integer>();
for(int num:nums)
{
map.put(num,map.getOrDefault(num, 0)+1);
}
System.out.println(map);
PriorityQueue<Integer> queue=new PriorityQueue<Integer>(k,new Comparator<Integer>()
{
@Override
public int compare(Integer o1, Integer o2)
{
//比较的是次数,从大到小,找前TOPK,所以用小顶堆
return map.get(o1).compareTo(map.get(o2));
}
});
//比较的数是key
for(int i:map.keySet())
{
queue.add(i);
//小顶堆的堆顶一定是最小的,poll出去的一定是最小的
if(queue.size()>k)
queue.poll();
}
return new ArrayList<Integer>(queue);
}
}