分治算法求序列中第K小数

题目

P1138 第 k 小整数

算法标签: 分治, 快速选择算法, $Partition$算法

思路

每次选择一个基准元素, 进行考虑

$Hoare$划分方法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 30010;

int n, k, w[N];
int cnt;
bool vis[M];

int find(int l, int r) {
   
    if (l == r) return w[l];
    int mid = w[l + r >> 1];
    int i = l - 1, j = r + 1;
    while (i < j) {
   
        while (w[++i] < mid);
        while (w[--j] > mid);
        if (i < j) swap(w[i], w[j]);
    }

    if (k <= j) return find(l, j);
    return find(j + 1, r);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
   
        int val;
        cin >> val;
        if (!vis[val]) {
   
            w[++cnt] = val;
            vis[val] = true;
        }
    }

    if (cnt < k) {
   
        cout << "NO RESULT" << "\n";
        return 0;
    }

    int ans = find(1, cnt);
    cout << ans << "\n";
    return 0;
}

*$Lomuto$划分方法

这个逻辑的边界问题处理非常麻烦

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 30010;

int n, k, cnt;
int w[N];
bool vis[M];

int find(int l, int r) {
   
    if (l == r && l == k) return w[l];
    if (l < k) {
   
        int val = w[l];
        int i = l, j = r;
        while (i < j) {
   
            while (i < j && w[j] > val) j--;
            if (i < j) swap(w[i], w[j]);
            while (i < j && w[i] <= val) i++;
            if (i < j) swap(w[i], w[j]);
        }

        w[i] = val;
        if (i == k) return w[k];
        else if (k < i) return find(l, i - 1);
        return find(i + 1, r);
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
   
        int val;
        cin >> val;
        if (!vis[val]) {
   
            w[++cnt] = val;
            vis[val] = true;
        }
    }

    if (cnt < k) {
   
        cout << "NO RESULT" << "\n";
        return 0;
    }

    int ans = find(1, cnt);
    cout << ans << "\n";
    return 0;
}