K-th smallest element in the list
Given
n integers and a number k, you are asked to find the k-th smallest element in the list. It’s guaranteed that the array elements are distinct.Input
The first line of the input contains two integers
n and k (1 ≤ k ≤ n ≤ ).The next line contains
n space-separated integers ().Output
The program should output the value of the
k-th smallest element in the given list.Examples
Input | Output |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Explanation
- The sorted list would be [-2, 3, 4, 6, 8, 10] ⇒ the 3rd smallest element would be 4
- The sorted list would be [-4, -3, 0, 5, 7, 8, 10] ⇒ the 2nd smallest would be -3
Hint 1
Use random partitioning similar to QuickSort.
Sorting elements is not viable under this time-limit constraint.
Hint 2
You can partition the array similar to QuickSort with a randomly chosen pivot. After which, you can keep only the part of the array that’s needed and ignore the other part.
This process can be repeated until the number of ignored elements BEFORE your current item is equal to
k.Random partitioning will actually have an expected linear time . Do you know why?
Hint 3
Each time we randomly partition the array, the expected size of the resulting array is half the current one. So, if the current array has a size of
n, after one partitioning we can throw away half of it - n/2, after two partitioning operations, we can throw away the other half - n/4, and so on. So, this sum becomes Yet, the algorithm can have a worst-case performance in case the randomly chosen elements don’t partition the array into an expected
n/2 size.Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB