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; } }