C# quickselect solution with random pivot (beats 93.33%)


  • 0
    K

    I converted the code in the following link to C# and made slight changes to it. It is a good example for the ones who are new to quickselect. And its performance is really good.
    http://www.geekviewpoint.com/java/search/quickselect

    public class Solution {
        public int FindKthLargest(int[] nums, int k) {
            return QuickSelect(nums,0,nums.Length-1,k-1);
        }
        public int QuickSelect(int[] nums,int first,int last,int k)
        {
            int pivot = partition(nums,first,last);
            if (pivot == k) 
                return nums[k];
            else if (pivot > k) 
                return QuickSelect(nums,first,pivot-1,k);
            else 
                return QuickSelect(nums,pivot+1,last,k);
        }
        public int partition(int[] nums,int first,int last)
        {
            Random rnd = new Random();
            int pivot = first + rnd.Next(last-first+1);
            swap(nums,pivot,last);
            for (int i=first;i<last;i++) {
                if (nums[i] > nums[last]) {
                    if (i != first) 
                        swap(nums,first,i);
                    first++;
                }
            }
            swap(nums,first,last);
            return first;
        }
        public void swap(int[] nums,int x,int y) {
            int tmp = nums[x];
            nums[x] = nums[y];
            nums[y] = tmp;
        }
    }
    

Log in to reply
 

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