TopK Elements和Kth Element问题

Kth Element

找出一个数组排好序后第K大的元素。

1. 排好序，然后得出第K大的元素。时间复杂度 O(NlogN)，空间复杂度 O(1)java public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; }

2. 使用堆

   • 父节点小于子节点的堆称之为小根堆，反之，父节点都大于子节点的堆称之为大根堆。
   • 堆的空间开销较树小，因为使用数组来实现的。

     //堆的创建
     //大顶堆
     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();
}

1. 使用快速选择（基于快排的思想）
   选择一个元素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){

    int j = partition(nums,l,h);
    if(j==k) break;
    if(j<k){
        l = j+1;
    }else{
        h = j-1;
    }

   } return nums[k]; }

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;
}