Kth Smallest Numbers in Unsorted Array

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.

Solution:

Same to Kth Largest Element. QuickSelect

Code:

class Solution {

    public int kthSmallest(int k, int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        return quickSelect(nums, 0, nums.length - 1, k - 1);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return nums[left];
        }
        int pivotIdx = left + (right - left) / 2;
        pivotIdx = partition(nums, left, right, pivotIdx);
        if (pivotIdx == k) {
            return nums[k];
        } else if (pivotIdx > k) {
            return quickSelect(nums, left, pivotIdx - 1, k);
        } else {
            return quickSelect(nums, pivotIdx + 1, right, k);
        }
    }

    private int partition(int[] nums, int left, int right, int pivotIdx) {
        int pivot = nums[pivotIdx];
        swap(nums, pivotIdx, right);
        int curIdx = left;
        while (left < right) {
            if (nums[left] <= pivot) {
                swap(nums, left, curIdx++);
            }
            left++;
        }
        swap(nums, right, curIdx);
        return curIdx;
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
};