分治-很大的数组的第K小

如果你有收获，请为这篇文章点个赞吧！

Description

求数组的第k小，数字数量非常多。

Input

每组数据给出n m k表示有n个数，求第k小，数组的数字由以下规则得到：

ai = mi mod  (109+7), i = 1, 2, …, n

其中 1 ≤ n, m ≤ 5 × 107, 1 ≤ k ≤ n，数据保证得到的数组元素大部分互不相等。

Output

输出第k小的数

Sample Input

3 2 2

Sample Output

4

Hint

先复习下快速排序的实现

实现代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<cmath>
#include<complex>
#include<vector>
#include<algorithm>
const int mod = 1e9 + 7;
const int maxn = 1e8 + 10;
int n, m, k;
int a[maxn];
int GetK(int left, int right, int k)
{
    if(left == right - 1) return a[left];
    int low = left, high = right - 1, center = a[low];
    while(low < high)
    {
        while(low < high && a[high] >= center) high --;
        a[low] = a[high];
        while(low < high && a[low] <= center) low ++;
        a[high] = a[low];
    }
    a[low] = center;
    if(low - left >= k) return GetK(left, low, k);
    else if(low - left + 1 == k) return a[low];
    else return GetK(low + 1, right, k - (low - left) - 1);
}
int main()
{
    while(scanf("%d%d%d", &n, &m, &k) != EOF)
    {
        a[0] = m;
        for(int i = 1; i < n; i ++)
            a[i] = 1LL * a[i - 1] * m % mod;
        printf("%d\n", GetK(0, n, k));
    }
    return 0;
}

© 著作权归作者所有,转载或内容合作请联系作者