[LintCode] 461 Kth Smallest Numbers in Unsorted Array 解题报告

Description
Find the kth smallest numbers in an unsorted integer array.


Example
Given [3, 4, 1, 2, 5], k = 3, the 3rd smallest numbers are [1, 2, 3].

Challenge 
An O(nlogn) algorithm is acceptable, if you can do it in O(n), that would be great.


思路
这题和Kth Largest Element （第K大就是第nums.length - K小）一模一样。
这里第K小个，对应的index就是K - 1。

Code

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
        return helper(nums, 0, nums.length - 1, k - 1);
    }
    
    public int helper(int[] nums, int lo, int hi, int k) {
        if (hi <= lo) {
            return nums[hi];
        }
        
        int pos = partition(nums, lo, hi);
        
        if (pos > k) {
            return helper(nums, lo, pos - 1, k);
        }
        else if (pos < k) {
            return helper(nums, pos + 1, hi, k);
        }
        
        return nums[pos];
    }
    
    public int partition(int[] nums, int lo, int hi) {
        if (hi <= lo) {
            return lo;
        }
        
        int lt = lo;
        int gt = hi;
        int i = lo + 1;
        
        int v = nums[lo];
        
        while (i <= gt) {
            if (nums[i] < v) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] > v) {
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
        
        return lt;
    }

    public void exch(int nums[], int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}