题解 | #寻找第K大#

小顶堆纯手写做法,时间和空间复杂度都很低。将数组的前k个位置作为一个k大小的小顶堆，维持a[0]为这个小顶堆的最小值，然后遍历堆之后的数字与a[0]比较，大于a[0]则交换两值位置并调整堆，遍历完成后则这个小顶堆就是最大的k个值，并且a[0]即为第k大的值。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        int heapSize = K;
        getHeap(a, K);
        for(int i = K; i < a.length; i++){
            if(a[i] > a[0]){
                swap(a, 0, i);
                minHeapify(a, 0, heapSize);
            }
        }
        return a[0];
    }
    private void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    private void minHeapify(int[] a, int i, int heapSize){
        int smallest = i, left = i * 2 + 1, right = i * 2 + 2;
        if(left < heapSize && a[left] < a[smallest]){
            smallest = left;
        }
        if(right < heapSize && a[right] < a[smallest]){
            smallest = right;
        }
        if(smallest != i){
            swap(a, i, smallest);
            minHeapify(a, smallest, heapSize);
        }
    }
    private void getHeap(int[] a, int heapSize){
        for(int i = heapSize/2 -1; i >= 0; i--){
            minHeapify(a, i, heapSize);
        }
    }
}