Find the kth smallest element in an unsorted array of non-negative integers.
Definition of kth smallest element
kth smallest element is the minimum possible n such that there are at least k elements in the array <= n. In other words, if the array A was sorted, then A[k - 1] ( k is 1 based, while the arrays are 0 based )
NOTE You are not allowed to modify the array ( The array is read only ). Try to do it using constant extra space.
Example:
A : [2 1 4 3 2]
k : 3
answer : 2
Method:
Search between 1 and INT_MAX
Solution:
Time: O(nlog32) ~ O(n) Space: O(1)
public class Solution { // DO NOT MODIFY THE LIST. IT IS READ ONLY public int kthsmallest(final List<Integer> A, int B) { int left = 1; int right = Integer.MAX_VALUE; while (left <= right) { int mid = left + (right - left) / 2; int smallerThanMid = 0; for (int i : A) { if (i <= mid) { smallerThanMid ++; } } if (smallerThanMid < B) { left = mid + 1; } else { right = mid - 1; } } return left; } }