Find the kth smallest numbers in an unsorted integer array.
Solution: quick select
public int kthSmallest(int k, int[] nums) {
if(nums == null || nums.length == 0 || k < 1){
return -1;
}
int start = 0, end = nums.length - 1, pos = 0;
while(start >= 0 && end < nums.length){
pos = partition(nums, start, end);
if(pos + 1 == k){
return nums[pos];
} else if(pos + 1 < k){
start = pos + 1;
} else{
end = pos - 1;
}
}
return nums[pos];
}
private int partition(int[] nums, int left, int right){
int l = left, r = right, pivot = nums[left];
while(l < r){
while(l < r && nums[r] >= pivot){
r--;
}
nums[l] = nums[r];
while(l < r && nums[l] <= pivot){
l++;
}
nums[r] = nums[l];
}
nums[l] = pivot;
return l;
}
.or:
public int kthLargestElement(int k, int[] nums) {
if(nums == null || nums.length < k || k < 1){
return 0;
}
return helper(nums, 0, nums.length - 1, k);
}
private int helper(int[] nums, int l, int r, int k){
int left = l, right = r;
int pivot = nums[left];
while(left < right){
while(left < right && nums[right] >= pivot){
right--;
}
nums[left] = nums[right];
while(left < right && nums[left] <= pivot){
left++;
}
nums[right] = nums[left];
}
nums[left] = pivot;
if(left == nums.length - k){
return nums[left];
} else if(left < nums.length - k){
return helper(nums, left + 1, r, k);
} else{
return helper(nums, l, left - 1, k);
}
}