美文网首页
215. Kth Largest Element in an A

215. Kth Largest Element in an A

作者: 窝火西决 | 来源:发表于2019-06-04 13:22 被阅读0次

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

    相关文章

      网友评论

          本文标题:215. Kth Largest Element in an A

          本文链接:https://www.haomeiwen.com/subject/kwpcxctx.html