461.Kth Smallest Numbers in Unsorted Array

1.Description(Medium)

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.

2.Code

Version 1: BruteForce O(nlogn)

Sort the array, return array[k-1];

Version 2: QuickSort