215. Kth Largest Element in an A

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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

题目

找数组里第K大的元素，这里指的是排好序后，从后往前数第k个数，是包含重复元素的。

思路

快排改造：
如果是有序数组，我们一下就能找到第k大的元素，但是所给数组无序，我们就需要先排序，但是又没必要全部排好序，所以可以依照快排思想，稍作改造，顺便复习一下快排。
快排思想：

1. 我们在数组里选择一个参考元素，这个参考元素一般选第一个元素，或者随机选一个把它和第一个元素换一下位置。
2. 两个指针分别从头尾遍历数组，如果头指针所指元素小于参考元素就继续往后走，尾指针所指元素大于参考元素就继续往前走，若不满足，则停下来，把两个指针元素交换位置，然后继续遍历，直到两指针相遇。
3. 遍历一次下来，数组左边的元素都小于等于参考元素，右边的元素都大于等于参考元素，此时再把参考元素（第一个）和两指针相遇位置的元素互换。就完成了第一次快排。
   此时数组为：[小于等于参考元素,...,参考元素,...,大于等于参考元素]。
4. 分别再对前半段数组和后半段数组重复上述123步骤，最后整个数组就排好了。

针对本题目，我们排完一次，可以判断一下指针的位置:

• 即数组右半边若刚好有k-1个元素，那么中间这个元素就是第k大的元素；
• 若数组右半边的元素数量<k-1个元素，说明第k大的元素在数组左半边；
• 若数组右半边的元素数量>k-1个元素，说明第k大的元素在数组右半边；
• 最后，依据上述不同情况，在特定区间递归寻找即可；

代码实现如下：

代码

 public int findKthLargest(int[] nums, int k) {
         int l=0;
         int r=nums.length-1;
        
           return  partition(l,r,nums,k);
        }

    private int partition(int start, int end, int[] nums,int k) {//快排分区
//      int random =(int)(Math.random()*(r-l+1)+l);
//      swap(nums,l,random);//先让第一个元素随机交换位置
        int i=start;
        int j=end;
        int v=nums[i];//这里我们就按照第一个元素划分
        while (i<j) {
            while (i<j&&nums[j]>=v) {//先让j往前走，遇到小于v的停下来。这里一定要先让j走！！
//因为i是从第一个元素开始的，而第一个元素的值已经存在v里了。所以先让j走，去覆盖i，没事。
                j--;
            }
            if(i<j)
                nums[i++]=nums[j];//与i交换，同时i往前走
            
            while (i<j&&nums[i]<=v) {//此时i再往后走,遇到大于v的就和j交换，此时j是指向从后往前第一个小于v的数，而且是已经复制过去了，所以这个值是重复的。
                i++;
            }
            if(i<j)
                nums[j--]=nums[i];
            //找到后交换位置
                        }
        nums[i]=v;//最后一步，把参考元素和指针交换，一轮就分完了
        if (k==end-j+1) {//从队尾到v一共k-1个元素的话，那么v就是第k大的元素
            return v;
        }else if (k<end-j+1) {//比v大的数已经超过k个了，所以第k大的数肯定在这里面
            return partition(j+1, end, nums, k);
        }else {//否则证明右边还没拍到第k大，所以在坐便继续找，这时注意我们在左边就是找（k-右边这么多元素）就够了
            return partition(start, j-1, nums, k-(end-j+1));
        }
        
    }