欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 215 Kth Largest Element in an Array

程序员文章站 2022-04-25 13:26:59
...

问题描述:

LeetCode 215 Kth Largest Element in an Array

解答:一开始我自己的思路,用一个长度为K的数组记录前K大的数字。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] temp=new int[k];
        Arrays.sort(nums,0,k);
        for(int i=0;i<k;i++) {
            temp[i]=nums[k-1-i];
        }
        for(int i=k;i<nums.length;i++){
            for(int j=0;j<k;j++){
                if(temp[j]<nums[i]){
                    change(temp,nums[i],j,k);
                    break;
                }
            }

        }
        return temp[k-1];
    }
    public static int[] change(int[] temp,int num,int j, int k){
        for(int i=k-1;i>j;i--){
            temp[i]=temp[i-1];
        }
        temp[j]=num;
        return temp;    
    }
}

后来,看了一种快排思想的思路。

这道题最好的解法应该是下面这种做法,用到了快速排序Quick Sort的思想,这里排序的方向是从大往小排。

核心思想是每次都要先找一个中枢点Pivot,然后遍历其他所有的数字,像这道题从大往小排的话,就把大于中枢点的数字放到左半边,把小于中枢点的放在右半边,这样中枢点是整个数组中第几大的数字就确定了,虽然左右两部分各自不一定是完全有序的,但是并不影响本题要求的结果,因为左半部分的所有值都大于右半部分的任意值,所以我们求出中枢点的位置。

如果中枢点的位置正好是k-1,那么直接返回该位置上的数字;如果大于k-1,说明要求的数字在左半部分,更新右边界,再求新的中枢点位置;反之则更新右半部分,求中枢点的位置;不得不说,这个思路真的是巧妙啊。。。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int left=0,right=nums.length-1;
        while(true){
            int pos=partition(nums,left,right);
            if(pos==k-1) return nums[pos];
            else if(pos>k-1) right=pos-1;
            else left=pos+1;
        }
    }
    public static int partition(int[] nums, int left,int right){
        int pivot=nums[left],l=left+1,r=right;
        int temp=0;
        while(l<=r){
            if(nums[l]<pivot && nums[r]>pivot){
                temp=nums[l];
                nums[l]=nums[r];
                nums[r]=temp;
                l++;
                r--;
            }
            if (nums[l] >= pivot) ++l;
            if (nums[r] <= pivot) --r;
        }        
        temp=nums[left];
        nums[left]=nums[r];
        nums[r]=temp;
        return r;
    }
}

其实时间上前一种12ms,后一种42ms。可能和pivot的选择关系比较大。