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].

Challenge

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

1. quicksort - o(nlogn)

public 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
        quickSort(0, nums.length - 1, nums);
        return nums[k - 1];
    }

    public void quickSort(int start, int end, int[] nums) {
        if (start >= end) {
            return;
        }

        int left = start;
        int right = end;
        int pivot = nums[(start + end) / 2];
        //make the two pointer pass each other to the opposing side to avoid overlap range
        while (left <= right) {
            //find the first item from left that is greater or EQUAL to the pivoit and stop there
            while (left <= right && nums[left] < pivot) {
                left++;
            }

            //same for the right
            while (left <= right && nums[right] > pivot) {
                right--;
            }

            //swap
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }

        quickSort(start, right, nums);
        quickSort(left, end, nums);

    }
}