[leetcode]Kth Smallest Element in an Array

利用QuickSelect的思想进行递归查找

QuickSelect:https://en.wikipedia.org/wiki/Quickselect

主要思想是借鉴QuickSort的分割思路，不同的是，QuickSelect只从一边进行遍历，以最后一个元素为pivot，将原无序数组分割为两部分

The basic idea is to use Quick Select algorithm to partition the array with pivot:

Put numbers < pivot to pivot's left Put numbers > pivot to pivot's right

Then

if indexOfPivot == k, return A[k] else if indexOfPivot < k, keep checking left part to pivot else if indexOfPivot > k, keep checking right part to pivot

Time complexity = O(n)

利用QuickSelect查找第k大的数，同理可以查找第k小的数

public class Solution { public int findKthLargest(int[] nums, int k) { return findKthLargest(nums,0,nums.length-1,k-1); } public int findKthLargest(int[] nums,int start,int end,int k){ if(start>end){ return Integer.MAX_VALUE; } int left = start; int pivotValue = nums[end]; for(int i=start;i<end;i++){ if(nums[i]>pivotValue){ if(left!=i){ swap(nums,left,i); } left++; } } swap(nums,left,end); if(left==k){ return nums[left]; }else if(left<k){ return findKthLargest(nums,left+1,end,k); }else return findKthLargest(nums,start,left-1,k); } public void swap(int[] nums,int i,int j){ int temp=nums[i]; nums[i] = nums[j]; nums[j] = temp; } }