LeetCode 215. Kth Largest Element in an Array

Kth Largest Element in an Array

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        return Find(nums, k, 0, nums.Length-1);
    }
    
    private int Find(int[] nums, int k, int left, int right){
        if(left == right) return nums[left];
        int cur = left;
        int l = left+1;
        int r = right;
        while(l < r){
            while(l <= right-1 && nums[l] < nums[cur]) l++;
            while(r >= left+2 && nums[r] >= nums[cur]) r--;
            if(l < r){
                Swap(nums, l, r);
            }
        }
        if(nums[l] < nums[cur]) {
            Swap(nums, l, cur);
            cur = l;
        } else {
            Swap(nums, l-1, cur);
            cur = l-1;
        }
        if(cur == nums.Length - k) return nums[cur];
        else if(cur < nums.Length - k) return Find(nums, k, cur+1, right);
        else return Find(nums, k, left, cur-1);
    }
    
    private void Swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *