问题

给出序列 $A[l,r]$ 求出其中第 $K$ 小的元素

解析

这里给出分治算法的做法

按 $5$ 个一组对整个序列分组排序，选出每组中的中间项
对所有的中项进行排序，选出中位数
用中位数进行划分
- 所有比中位数小的放到中位数前面，比中位数大的放到中位数后面
- 若前面的数少于 $K-1$ 个，则在后半部分寻找第 $k-leftsize$ 个，其中 $leftsize$ 表示前半部分的元素个
- 若前面的数等于 $K-1$ 个，则当前所选取的中位数就是答案
- 若前面的数多于 $K$ 个，则在前半部分寻找第 $K$ 小
  设计

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<ll, ll> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("..\\input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];

int Partition(int a[], int l, int r)
{
    int p = a[l];
    while (l < r)
    {
        while (l < r && a[r] >= p)
            --r;
        a[l] = a[r];
        while (l < r && a[l] <= p)
            ++l;
        a[r] = a[l];
    }
    a[l] = p;
    return l;
}

int select_rank_k(int a[], int l, int r, int k)
{
    int g = (r - l + 5) / 5;
    int ret = l;
    for (int i = l; i <= r; i += 5)
    {
        sort(a + i, a + i + min(5, r - i + 1));
        swap(a[ret++], a[i + min(5, r - i + 1) / 2]);
    }
    sort(a + l, a + l + g);
    swap(a[l], a[l + g / 2]);
    int cur = Partition(a, l, r) - l;
    if (cur == k - 1)
        return a[l + cur];
    else if (cur < k)
        return select_rank_k(a, cur + 1, r, k - cur - 1);
    else
        return select_rank_k(a, l, cur - 1, k);
}
int main()
{
    int A[15] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
    printf("%d\n", select_rank_k(A, 0, 4, 4));
    return 0;
}

分析

考虑这么做的复杂度

第一部分，对于每 $5$ 个元素进行排序，由于排序元素个数固定，这一部分的复杂度可以认为是 $O(\log_2^5n)$
第二部分，对于每个中间项的排序，对于长度为 $n$ 的序列，共有 $\lceil\frac{n}{5}\rceil$ 个中间项对这 $\lceil\frac{n}{5}\rceil$ 个元素重复上述过程，直到只剩下一个元素，这个元素会是第一部分中位数的中位数
第三部分，划分的复杂度为 $O(n)$ ，因为每个数字都会且仅会被比较一次
第四部分，考虑最坏的情况，至少有 $3\times\frac{\lceil\frac{n}{5}\rceil}{2}$ 个元素小于所选取的中位数，所以此时的复杂度 $T(n)=T(\frac{7n}{10})+G(n)$ 其中 $G(n)$ 是前三部分的复杂度之和

先考虑 $G(n)$

第一和第三部分的复杂度都等价于
- 可以得到 $G(n)=\frac{n}{5}+G(\frac{n}{5})$
- 列项累加 $\left.\begin{align*} G(n)&=\frac{n}{5}+G(\frac{n}{5})\\ G(\frac{n}{5})&=\frac{n}{25}+G(\frac{n}{25})\\ &\dots\\ G(1)&=1 \end{align*}\right.$
- 则原式 $\left.\begin{align*}G(n)&=n\times(\sum_{i}{\frac{1}{5^i}})\\ &=n\times\frac{\frac{1}{5}(1-\frac{1}{5}^q)}{1-\frac{1}{5}}\\ &=\frac{n}{4} \end{align*}\right.$
- 所以第三部分的复杂度也是 $O(n)$
总的 $G(n)\sim O(n)$

上方代码我偷懒直接sort了，可以递归做的

计算总复杂度

$T(n)=T(\frac{7n}{10})+O(n)$
可以列出方程 $\left.\begin{align*} T(n)&=T(\frac{7n}{10})+O(n)\\ T(\frac{7n}{10})&=T(\frac{49n}{100})+O(\frac{7n}{10})\\ &\dots\\ T(1)&=1 \end{align*}\right.$
原式可以转化为 $\left.\begin{align*} T(n)&=n\times\sum_{i=0}\left(\frac{7}{n}\right)^i\\ &=n\times\left(\frac{1-\left(\frac{7}{10}\right)^k}{1-\frac{7}{10}}\right)\\ &=n\times\frac{10}{3} \end{align*}\right.$
所以最终的复杂度 $T(n)\sim O(n)$

源码

传送门

算法课-第k小分治算法

问题

解析

设计

分析

源码