Quick select with three way partitioning for dup handling (c#)


  • 0
    R

    c#

    public int FindKthLargest(int[] nums, int k) {
    return findK(nums,k-1,0,nums.Length-1);
    }

    private int findK(int[] nums, int k, int s, int e)
    {
        //array is sorted in three parts: 
       //large is on the left, pivot w/ dups in the middle, and smaller on the right
       //variable large is the index of the first pivot element from the left
       //variable i points to the first be sorted element in the array from the left
       //variable j points to the first to be sorted element in the array from the right
      //choose the value of the first element as pivot
        int i = s, j = e;
        int larger = i, large = j, pivot = nums[i];
        while (i <= j)
        {
            if (nums[i] > pivot)
            {
                Swap(nums, larger++, i++);
            }
            else if (nums[i] < pivot)
            {
                Swap(nums, i, j--);
            }
            else i++;
        }
        //if k is between the first and last pivot, any element satisfies,so return true
        if (k >= larger && k < i)
            return nums[k];
        else if (k < larger) //the large element count on the left is greater than k, increase pivot
            return findK(nums, k, s, larger - 1);
        else//the larger element count on the right is less than k, reduce pivot (i is the first one after pivot)
            return findK(nums, k, i, e);
    }
    
    private void Swap(int[] nums, int i, int j)
    {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

Log in to reply
 

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