K-th smallest element in the list
nintegers 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.
The first line of the input contains two integers
k(1 ≤ k ≤ n ≤ ).
The next line contains
nspace-separated integers ().
The program should output the value of the
k-th smallest element in the given list.
6 3 10 -2 4 8 3 6
7 2 -4 5 8 -3 10 0 7
- 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
Use random partitioning similar to QuickSort.
Sorting elements is not viable under this time-limit constraint.
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
Random partitioning will actually have an expected linear time . Do you know why?
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
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB