main函数
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int n, k;
scanf("%d%d", &n, &k);
if (n <= 0 || k <= 0 || k > n) {
puts("");
return 0;
}
vector<int> vec(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &vec[i]);
}
quickSelect(&vec[0], 0, n - 1, k);
printf("%d\n", vec[k - 1]);
return 0;
}
左右指针不取右,j和j+1
void quickSelect(int* arr, int left, int right, int k) {
if (left >= right) {
return;
}
int pivot = arr[left + ((right - left) >> 1)];
int i = left - 1;
int j = right + 1;
while (i < j) {
while (arr[++i] < pivot) {
}
while (arr[--j] > pivot) {
}
if (i < j) {
swap(arr[i], arr[j]);
}
}
int leftSize = j - left + 1;
if (k <= leftSize) {
quickSelect(arr, left, j, k);
return;
}
quickSelect(arr, j + 1, right, k - leftSize);
}
左右指针不取左,i-1和i
void quickSelect(int* arr, int left, int right, int k) {
if (left >= right) {
return;
}
int pivot = arr[(static_cast<int64_t>(left) + right + 1) >> 1];
int i = left - 1;
int j = right + 1;
while (i < j) {
while (arr[++i] < pivot) {
}
while (arr[--j] > pivot) {
}
if (i < j) {
swap(arr[i], arr[j]);
}
}
int leftSize = i - left;
if (k <= leftSize) {
quickSelect(arr, left, i - 1, k);
return;
}
quickSelect(arr, i, right, k - leftSize);
}
快慢指针取左
void quickSelect(int* arr, int left, int right, int k) {
if (left >= right) {
return;
}
int pivot = arr[left];
int i = left;
int j = left + 1;
while (j <= right) {
if (arr[j] < pivot) {
++i;
swap(arr[i], arr[j]);
}
++j;
}
swap(arr[i], arr[left]);
int leftSize = i - left + 1;
if (k == leftSize) {
return;
}
if (k < leftSize) {
quickSelect(arr, left, i - 1, k);
return;
}
quickSelect(arr, i + 1, right, k - leftSize);
}
快慢指针取右
void quickSelect(int* arr, int left, int right, int k) {
if (left >= right) {
return;
}
int pivot = arr[right];
int i = left - 1;
int j = left;
while (j < right) {
if (arr[j] < pivot) {
++i;
swap(arr[i], arr[j]);
}
++j;
}
++i;
swap(arr[i], arr[right]);
int leftSize = i - left + 1;
if (k == leftSize) {
return;
}
if (k < leftSize) {
quickSelect(arr, left, i - 1, k);
return;
}
quickSelect(arr, i + 1, right, k - leftSize);
}