215. Kth Largest Element in an Array

1.使用总容量为k+1的优先队列维护值最大的k个点，一旦总数量Y超过k，移除Y中值最小的点。堆中插入和删除的最差时间为O(log(k),log(k)为堆的高度，又因为遍历整个数组，所以时间复杂度为n*log(k)，不会修改输入数组。

public int findKthLargest(int[] nums, int k) {
    // min heap by default
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for (int num : nums) {
        q.offer(num);
        if (q.size() > k) {
            q.poll();
        }
    }
    return q.peek(); // 堆顶记录第k大的元素
}

• 使用offer()或者add()方法时会进行排序，这里维护一个小堆。poll()方法移除优先级最高的点，这里是最小值

• 最大堆可以用Collection.reverseOrder()这个comparator，别的自定义对象需要自己实现comparator

PriorityQueue<Integer> q = new PriorityQueue<>(nums.length, Collection.reverseOrder());
// max heap
PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);

一个例子

input: {3,2,1,5,6,4}, 3

Befor pop: [3]
After pop: [3]
Befor pop: [2, 3]
After pop: [2, 3]
Befor pop: [1, 3, 2]
After pop: [1, 3, 2]
Befor pop: [1, 3, 2, 5]
After pop: [2, 3, 5]
Befor pop: [2, 3, 5, 6]
After pop: [3, 6, 5]
Befor pop: [3, 4, 5, 6]
After pop: [4, 6, 5]
return 4

partition做法，在数组中随机取一个数字pivot=num[l]作为基准将其partition成左右两部分，左边比num[l]小，右边比num[l]大，分割完后计算左边数字的长度，也就是比较返回值mid(注意mid是数组下标)和k-1的关系，如果mid > k - 1，说明左边的长度较长，缩小右边界长度，使r = mid - 1，继续在左边寻找，用一句话总结就是边界需要向k - 1靠近。时间O(n)，会修改输入数组。注意边界。。。。。。。。。。。。。。。。。

public int findKthLargest(int[] nums, int k) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = partition(nums, l, r);
        if (mid == k - 1) return nums[mid];
        else if (mid > k - 1) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

public int rand(int[] nums, int l, int r) {
    Random random = new Random();
    int randomIndex = random.nextInt(r - l + 1) + l;
    swap(nums, l, randomIndex);
    return nums[l];
}

public int middleOfThree(int[] nums, int l, int r) {
    int mid = (l + r) >>> 1;
    if (nums[l] < nums[r]) swap(nums, l, r); // l > r
    if (nums[mid] < nums[r]) swap(nums, mid, r); // m > r
    if (nums[mid] < nums[l]) swap(nums, mid, l); //m > l
    return nums[l];
}

public void swap(int[] nums, int l, int r) {
    int tmp = nums[l];
    nums[l] = nums[r];
    nums[r] = tmp;
}

// 从大到小排列
public int partition(int[] nums, int l, int r) {
    int pivot = middleOfThree(nums, l, r);
    // int pivot = rand(nums, l, r);
    while (l < r) {
        while (l < r && nums[r] <= pivot) r--;
        nums[l] = nums[r];
        while (l < r && nums[l] >= pivot) l++;
        nums[r] = nums[l];
    }
    nums[l] = pivot;
    return l;
}

例子[3,2,3,1,2,10,4,100,20,30,5,5,6], k=4

[6, 2, 3, 3, 2, 10, 4, 100, 20, 30, 5, 5, 1]
[30, 20, 100, 10, 6, 2, 4, 3, 3, 2, 5, 5, 1]
[30, 20, 100, 10, 6, 2, 4, 3, 3, 2, 5, 5, 1]
out = 10

其他的坑：小堆，大堆。。