Theory
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
class QuickSelect {
private:
int partition(vector<int>& A, int left, int right, int pivotIndex) {
int pivotValue = A[pivotIndex];
std::swap(A[pivotIndex], A[right-1]);
int nextIndex = left;
for (int i = left; i + 1 < right; i++) {
if (A[i] < pivotValue) {
std::swap(A[nextIndex], A[i]);
nextIndex++;
}
}
std::swap(A[nextIndex], A[right-1]);
return nextIndex;
}
int select(vector<int>& A, int left, int right, int k, std::mt19937& gen) {
if (left + 1 == right) {
return A[left];
}
int size = right - left;
int64 rnd = static_cast<int64>(gen()) % size;
int pivotIndex = left + rnd;
pivotIndex = partition(A, left, right, pivotIndex);
if (k == pivotIndex + 1) {
return A[pivotIndex];
} else if (k < pivotIndex + 1) {
return select(A, left, pivotIndex, k, gen);
}
return select(A, pivotIndex + 1, right, k, gen);
}
public:
int findKthSmallest(vector<int>& nums, int k) {
std::random_device rd;
std::mt19937 gen(rd());
return select(nums, 0, nums.size(), k, gen);
}
};
Practice
