description: Find the kth smallest numbers in an unsorted integer array.
Have you met this question in a real interview? Yes Example Given [3, 4, 1, 2, 5], k = 3, the 3rd smallest numbers are [1, 2, 3].
使用quick sort的方式进行处理
class Solution { /* * @param k an integer * @param nums an integer array * @return kth smallest element */ public int kthSmallest(int k, int[] nums) { // write your code here if (nums == null || nums.length == 0) { return -1; } if (nums.length < k) { return -1; } int left = 0; int right = nums.length - 1; util(nums, left, right); return nums[k - 1]; } PRivate void util(int[] nums, int left, int right) { if (left >= right) { return; } int start = left; int end = right; int pivot = nums[(left + right) / 2]; while (left <= right) { while (left <= right && nums[left] < pivot) { left++; } while (left <= right && nums[right] > pivot) { right--; } if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } util(nums, start, right); util(nums, left, end); }}新闻热点
疑难解答
