本文主要是介绍LintCode Kth Smallest Number in A Unsorted Array,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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 hereif (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);}
}
这篇关于LintCode Kth Smallest Number in A Unsorted Array的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!