Using partition to search for the kth in C accepted as best


  • 0

    If you are unclear about the partition in quick sort, you should check this simple post.

    Actually if you just sort this array by quick sort and return the kth it will also be the best submission


    void swap(int* p, int* q)
    {
        int t=*p; *p=*q; *q=t;
    }
    
    int partition(int* nums, int begin, int end)
    {
        int l=begin, r=end;
        int m = (l+r)/2;
        int mid = nums[m];
        swap(nums+m, nums+l);
        l++;
        while(l <= r)
        {
            while(nums[r] > mid) r--;
            while(l<=r && nums[l]<mid) l++;
            if(l <= r)
            {
                swap(nums+l, nums+r);
                l++; r--;
            }
        }
        swap(nums+begin, nums+r);
        return r;
    }
    
    //AC - 4ms;
    int findKthLargest(int* nums, int size, int k)
    {
        k = size-k;
        int begin = 0; 
        int end = size-1;
        while(true)
        {
            int position = partition(nums, begin, end);
            if(position == k) return nums[k];
            if(position > k) end = position-1;
            else begin = position+1;
        }
    }
    

    Using quick sort to solve this.


    void sort(int* nums, int begin, int end)
    {
        int l=begin, r=end;
        int v = nums[(r+l)/2];
        while(l <= r)
        {
            while(nums[l] < v) l++;
            while(nums[r] > v) r--;
            if(l <= r)
            {
                int t=nums[l]; nums[l]=nums[r]; nums[r]=t;
                l++; r--;
            }
        }
        if(begin < r)
            sort(nums, begin, r);
        if(l < end)
            sort(nums, l, end);
    }
    //AC - 4ms;
    int findKthLargest(int* nums, int size, int k) {
        sort(nums, 0, size-1);
        return nums[size-k];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.