Kth Element
找出一个数组排好序后第K大的元素。
排好序,然后得出第K大的元素。时间复杂度 O(NlogN),空间复杂度 O(1)
java public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; }
使用堆
- 父节点小于子节点的堆称之为小根堆,反之,父节点都大于子节点的堆称之为大根堆。
- 堆的空间开销较树小,因为使用数组来实现的。
//堆的创建
//大顶堆
PriorityQueue<Integer> maxheap = new PriorityQueue<>((o1,o2)->o2-o1);
//小顶堆
PriorityQueue<Integer> minheap = new PriorityQueueM<>();
使用堆来解决Kth Element问题,时间复杂度 O(NlogK),空间复杂度 O(K)。
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minheap = new PriorityQueue<>();
for(int n:nums){
minheap.add(n);
if(minheap.size()>k){
minheap.poll();
}
}
return minheap.peek();
}
- 使用快速选择(基于快排的思想)
选择一个元素j
,并确定好他的位置,使左边的元素都小于它,右边的元素大于它。再将它与K(在Kth Element问题中,要将k = nums.length-k,因为是求第K大的元素,而不是求第K小的元素)进行比,若该元素j
小于K则调整左边界,若大于K则调整右边界,等于则表示该元素为第K大的元素。```java public int findKthLargest(int[] nums, int k) { k = nums.length-k;//求第K大的元素 int l = 0;int h = nums.length-1; while(l<h){
} return nums[k]; }int j = partition(nums,l,h);
if(j==k) break;
if(j<k){
l = j+1;
}else{
h = j-1;
}
private int partition(int a[],int l,int h){ int i = l;int j = h+1; while(true){ while(a[++i]a[l]&&j>l); if(i>=j){ break; }else{ swap(a,i,j); } } swap(a,j,l); return j; }
<a name="d39a1ca1"></a>
## TopK Elements
1. 使用堆:TopK即求最小的K个元素,则可以使用大小为K的大顶堆来实现(若一个元素比这K个元素里最大的要小,则这个元素暂时属于TopK里的),当遍历到一个新元素时,把该元素与堆顶元素进行比较,若小于大顶堆的堆顶,则poll该堆再把元素加进去。
1. 使用快速选择,类似于Kth Element,得出第K大的元素,再遍历一次数组,所有小于Kth的元素都属于TopK。
<a name="2FfTJ"></a>
## TopK Frequent Element
使用桶来存储元素(key)以及元素响应出现的次数(value),再用小顶堆解决TopK的问题。
```java
public int[] topKFrequent(int[] nums, int k) {
Hashmap<Integer,Integer> count = new Hashmap<>();
for(int n:nums){
count.put(n,count.getOrDefault(n,0)+1)
}
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->count.get(o1)-count.get(o2));
for(int n:count.keySet(n){
queue.add(n);
if(queue.size()>k){
queue.poll();
}
}
int[] result = new int[k];
for(int i = k-1;i>=0;i--){
result[i] = queue.poll();
}
return result;
}