每日一题-15th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

LuoGu P1923. 求第 k 小的数

题目描述

输入 $n$（$1 \le n < 5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1 \le a_i < {10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 0 小。

样例

样例 1 输入

1 2	5 1 4 3 2 1 5

样例 1 输出

思路和实现

最好想的方法是快速排序，再索引找，这种方法时间 $O(n\cdot log\space n)$，空间 $O(log\space n)$；但这稍微卡一下时间就不行，必须比快排更快一点；

回忆数据结构书上的内容，有两种做法：

使用最小化堆作优先级队列，建堆并出队 $k+1$ 次即可，时间 $O(n+k\cdot log(n))$，空间 $O(1)$（存储原始数据的空间不算辅助空间）；

#include <iostream>
using namespace std;

void percolateDown(int* arr, int idx, int size) {
    int next = 2 * idx + 1; int tmp = arr[idx];
    while (1) {
        if (next + 1 < size && arr[next] > arr[next + 1]) ++next;
        if (next >= size || arr[next] > tmp) {
            arr[idx] = tmp; break;
        }
        arr[idx] = arr[next]; idx = next; next = 2 * idx + 1;
    }
}

int main() {
    int n, k; cin >> n >> k;
    int* arr = new int[n] {0};
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    for (int i = (n - 1) / 2; i >= 0; --i)
        percolateDown(arr, i, n);
    // 无需使用堆排序的办法，因为不要求保留原来的数据
    for (int i = 0; i < k; ++i) {
        arr[0] = arr[n - i - 1];
        percolateDown(arr, 0, n - i - 1);
    }
    cout << arr[0];
    delete[] arr;
    return 0;
}

使用最大化堆作优先级队列，先以前 $k+1$ 项建堆，后 $n-k-1$ 项依次与队头比较：队头较大则出队，将当前数据进队；结束后队列中 $k+1$ 个数是数组中前 $k+1$ 小的数，所以队头是第 $k$ 小的数（题干说最小的数是第 0 小）；时间 $O(n\cdot log(k))$，空间 $O(1)$；

#include <iostream>
using namespace std;

void percolateDown(int* arr, int idx, int size) {
    int next = 2 * idx + 1; int tmp = arr[idx];
    while (1) {
        if (next + 1 < size && arr[next] < arr[next + 1]) ++next;
        if (next >= size || arr[next] < tmp) {
            arr[idx] = tmp; break;
        }
        arr[idx] = arr[next]; idx = next; next = 2 * idx + 1;
    }
}

int main() {
    int n, k; cin >> n >> k;
    int* arr = new int[n] {0};
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    for (int i = k / 2; i >= 0; --i)
        percolateDown(arr, i, k + 1);
    for (int i = k + 1; i < n; ++i) {
        if (arr[i] < arr[0]) {
            int tmpOut = arr[0], tmpIn; arr[0] = arr[k];    // 先出队
            percolateDown(arr, 0, k);
            tmpIn = arr[k] = arr[i]; int cur = k, nxt = (cur - 1) / 2;
            while (1) {    // 再入队
                if (cur == 0 || arr[nxt] > tmpIn) {
                    arr[cur] = tmpIn; break;
                }
                arr[cur] = arr[nxt]; cur = nxt; nxt = (cur - 1) / 2;
            }
            arr[i] = tmpOut;    // 没必要，但是这样做不损失数据
        }
    }
    cout << arr[0];
    delete[] arr;
    return 0;
}

您猜怎么着？两个都超时了…… 这出题人明显是压时间了（咬牙切齿😬），看起来时间不做到完全 $O(n)$ 是没法通过的！

上面两个方法会慢一点的原因是，实际上这两种算法还是涉及到了排序的因素，而排序是不必要的，意味着不完全的排序来得到答案，可能花费的时间更少；

快排思想：先进行一轮快排，通过个数计算 第 $k$ 小的数在左右区间的哪个部分，只判断一个部分，这样（$T(n)=T(\dfrac{n}{2})+O(n)$）就能快于快排。时间平均 $O(n)$；最坏 $O(n^2)$；

#include <iostream>
using namespace std;

int divide(int* arr, int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (arr[right] > pivot && left < right) --right;
        if (left < right) arr[left] = arr[right];
        while (arr[left] <= pivot && left < right) ++left;
        if (left < right) arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

void quickGetK(int* arr, int left, int right, int k) {
    if (left >= right) return;
    int mid = divide(arr, left, right);
    if (mid == k) return;
    else if (mid < k) quickGetK(arr, mid + 1, right, k);
    else quickGetK(arr, left, mid - 1, k);
}

int main() {
    int n, k; cin >> n >> k;
    int* arr = new int[n] {0};
    for (int i = 0; i < n; ++i) cin >> arr[i];
    quickGetK(arr, 0, n - 1, k);
    cout << arr[k];
    delete[] arr;
    return 0;
}

结果，有一个测试集不超时了，还有一个仍然超时……行，方向是对的，那么再把臭名昭著的 cin 和 cout 替换成 prinf 和 scanf；

#include <bits/stdc++.h>
using namespace std;

int divide(int* arr, int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (arr[right] > pivot && left < right) --right;
        if (left < right) arr[left] = arr[right];
        while (arr[left] <= pivot && left < right) ++left;
        if (left < right) arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

void quickGetK(int* arr, int left, int right, int k) {
    if (left >= right) return;
    int mid = divide(arr, left, right);
    if (mid == k) return;
    else if (mid < k) quickGetK(arr, mid + 1, right, k);
    else quickGetK(arr, left, mid - 1, k);
}

int main() {
    int n, k; scanf("%d%d", &n, &k);
    int* arr = new int[n] {0};
    for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
    quickGetK(arr, 0, n - 1, k);
    printf("%d", arr[k]);
    delete[] arr;
    return 0;
}