215. Kth Largest Element in an Array (Medium)

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given[3,2,1,5,6,4]and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution 1: Quick Select Two Pointers O(n) average, O(n^2) worst; O(1)

worst: choose the largest num as the pivot each time，which is hard to construct.

T(n) = T(n/2) + O(n) = O(n) + O(n/2) + O(n/4) + ……+ O(1) = O(n) 这里算的是平均时间复杂度，不是worst。

我们来算一个理想状况，假如每次都平分，这样时间复杂度展开是 O(n + n/2 + n/4 + ... .+1) = O(2n) = O(n)。因为算法是，挑选一个pivot之后，O(n)时间进行partition，然后判断一下第k大在左边还是在右边。然后继续往下进行，那么理想情况下，无论去左边还是去右边，规模都从 n 变成了 n / 2。所以 T(n) = T(n/2) + O(n) = O(n)

如果不理想的情况，运气很不好的话，每次的pivot 都取到了最大或者最小的值，那么复杂度展开是 O(n + n-1 + n-2 + n-3 ... + 1) = O(n^2)。那么我们应该怎么衡量这个算法的时间复杂度呢？类似快速排序我们认为是 O(nlogn)的，因为我们算的是平均时间复杂度，也就是平摊一下各种情况的概率和时间复杂度。因为并不一定每次都运气那么不好，比如你用随机的方式挑选 pivot的话，这样我们认为 quick select 的时间复杂度均摊是 O(n)的。

https://www.jiuzhang.com/qa/6206/

During quick select, choose a number as the pivot, which is the middle number of array here .
Since Kth Largest Element is the kth element in descending order, start from left to find a number that is smaller than or equal to pivot. And from right to find a number that is larger than or equal to pivot. Next, swap them.
Repeat until we find the target. 这里很敷衍，解释清楚要很长时间，建议写完代码再go through一个例子。

[3, 2, 1, 5, 6, 4] k = 2, return 5.
left = 0, right = 5, l = 0, r = 5, pivot = 1, 1和4换=> [3, 2, 4, 5, 6, 1] l = 5, r = 4,第一次while结束，
此时，left + k - 1 = 1 < r, 执行 quickSelect(nums, 0, 4, 2);

left = 0, right = 4, l = 0, r = 4, pivot = 4, 3和6换=> [6, 2, 4, 5, 3, 1] 
l = 1, r = 3, 2和5换=>[6, 5, 4, 2, 3, 1] l = 2, r = 2, 4和4交换, l = 3, r= 1, 第二次while结束
此时，left + k - 1 = 1 <= r, 执行 quickSelect(nums, 0, 1, 2);

left = 0, right = 1, l = 0, r = 1, pivot = 6, while 开始后，l = 1, r = 1, 5和5交换，l = 2, r = 0. 第三次while结束
此时，left + k - 1 = 1 > r 且 < l, 返回nums[r+1], 即nums[1]

全部输出如下：
[3, 2, 4, 5, 6, 1]
[3, 2, 4, 5, 6, 1]
[6, 2, 4, 5, 3, 1]
[6, 5, 4, 2, 3, 1]
[6, 5, 4, 2, 3, 1]
[6, 5, 4, 2, 3, 1]

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (k <= 0 || k > nums.length) { //important!
            return -1;
        }

        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) { //九章写法。效率高，5ms
        if (left == right) {
            return nums[left];
        }

        //以下一块代码和Quick Sort的代码一样，功能是Partition，只不过pivot前的符号相反，因为这里是从大到小排序
        int l = left, r = right;
        int pivot = nums[l + (r - l) / 2]; //[3,2,1,5,6,4] pivot = 1
        while (l <= r) { 
            while (l <= r && nums[l] > pivot) {//从左边开始找小于等于pivot的数，因为最后要形成降序，左大右小
                l++;
            }
            while (l <= r && nums[r] < pivot) {//从右边开始找大于等于pivot的数
                r--;
            }
            if (l <= r) { //必须要有=，否则l++和r--不能执行，会造成死循环。
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            }
            //System.out.println(Arrays.toString(nums));
        }

        //在上面循环结束后，l可能=r+1(相邻)，也可能l=r+2（中间隔一个）
        if (left + k - 1 <= r) { //k是第几大，k-1是索引，这个条件表示k在左边
            return quickSelect(nums, left, r, k);
        }
        if (left + k - 1 >= l) { //这个条件表示k在右边
            //k - (l - left)：要减掉左边的部分，比如找第5大，左边3个数，那只要在剩下部分找第2大数即可。
            return quickSelect(nums, l, right, k - (l - left)); 
        }
        return nums[r + 1]; //到这步，说明k在r和l中间，即k=r+1。
    }

夜皇雪写法，有例子，好解释。但是效率低，70ms左右，太慢，放弃。

/**
* 3,2,1,5,6,4 k = 3
* 0 1 2 3 4 5
pivot : 3 [3, 2, 1, 5, 6, 4]
[3, 4, 6, 5, 1, 2] 3

pivot : 5 [5, 4, 6, 3, 1, 2]
[5, 6, 4, 3, 1, 2] 1

pivot : 4 [6, 5, 4, 3, 1, 2]
[6, 5, 4, 3, 1, 2] 2
*/

    public int findKthLargest(int[] nums, int k) { //夜皇雪写法，有例子，好解释。但是效率低，70ms左右，太慢，放弃。
        if (nums == null || nums.length == 0) return 0;
        int left = 0;
        int right = nums.length - 1;
        while (true) {
            int index = partition(nums, left, right);
            if (index + 1 == k) {
                return nums[index];
            }
            if (index + 1 > k) {
                right = index - 1;
            } else {
                left = index + 1;
            }
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int l = left + 1;
        int r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot) {
                swap(nums, l++, r--);
            }
            if (nums[l] >= pivot) l++;
            if (nums[r] <= pivot) r--;
        }
        swap(nums, left, r);
        return r;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

Solution 2: minHeap O(n log k); O(k)

    /**
     * minHeap O(nlogk);O(k)
     * Create a min heap as a window.
     * For each number in the array, add it to the heap.
     * If heap size > k, poll from the heap.
     * Return the top of the heap at the end.
     */
    public int findKthLargestB(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (k <= 0 || k > nums.length) {
            return -1;
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) { //每次弹出最小的，最后剩下k个数就是最大的k个数
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

Follow Up:

1.Smallest

Quick Select: "nums.length - k" to k; minHeap: k -> nums.length - k + 1

2.what if n is much greater than k. 比如n=1000000000，k=10
只能用Solution2: 用minHeap维护前k个, O(n log k); O(k) n个元素插入heap的复杂度是O(n)

以下想法不对，因为不太可能维护这么大的堆：用heap维护所有的n个，然后poll k次，这样时间复杂度是klogn

3.如果是input是steaming的话思路是什么，问了复杂度

同2