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]
.
An O(nlogn) algorithm is acceptable, if you can do it in O(n), that would be great.
class Solution {
public:
/\*
\* @param k an integer
\* @param nums an integer array
\* @return kth smallest element
\*/
int kthSmallest\(int k, vector<int> nums\) {
// write your code here
int start = 0, end = nums.size\(\) - 1;
while \(true\) {
if \(start > end\) {
break;
}
int i = start, j = start, l = end + 1;
int pivot = nums\[start + \(end - start >> 1\)\];
while \(i < l\) {
if \(nums\[i\] < pivot\) {
swap\(nums\[i++\], nums\[j++\]\);
} else if \(nums\[i\] == pivot\) {
++i;
} else {
swap\(nums\[i\], nums\[--l\]\);
}
}
if \(k - 1 < j\) {
end = j - 1;
} else if \(k - 1 >= l\) {
start = l;
} else {
return pivot;
}
}
return -1;
}
};