Java教程

快速选择算法(找到第k个数字)

本文主要是介绍快速选择算法(找到第k个数字),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

  在一个给定的乱序的序列中找到第k个数字,可能会想到先排序,然后输出第k个数。这种方法简单粗暴,时间复杂度为O(nlogn)。

  还有一种方法是快速选择,它的思想和快速排序很相似。就是先选择一个数x,然后把这个序列分成左右两边,其中左边的所有的数都<=x,右边的数都>=x。然后比较左边数字的个数leftNum与k的大小。如果k <= leftNum,说明我们要找到第k个数在调整后的序列的左边那部分;否则就是在右边的那部分。然后再用相同的方法递归那部分来找到第k个数。

  我们在这个序列中随便找到一个数x,接下来和快速排序一样,把这个序列调整为左边的部分的数都<=x,右边部分的数都>=x。

  其中指针j就为划分左右两边的下标位置,j的左边(包括j这个位置)就是左部分,右边就是右部分。

  接下来计算左边部分元素的个数leftNum = j - left + 1,与k进行比较:

  • 如果k <= leftNum,说明我们要找的第k个数就在左边部分,递归去在左边部分找第k个数,寻找序列的下标范围是[left, j];
  • 否则如果k > leftNum,说明我们要找的第k个数在右边部分,这时应该是递归去在右边部分找第k - leftNum个数,相应的寻找序列的下标范围应该为[j + 1, right]。

  快速选择算法的时间复杂度为O(n)。

  可以试想假设序列有n个元素,开始的第一次寻找次数为n,然后把序列分成左右两部分,有相关证明两边的期望大小各为为n/2,我们要在其中的一部分找。然后同样的方法又分成两部分,为n/4。以此类推,所以有

\[n + \frac{n}{2} + \frac{n}{4} + ... = n (1 + \frac{1}{2} + \frac{1}{4} + ...) = n\lim_{m->\infty }\sum_{i = 1}^{m} \frac{1}{2^{i}} = 2n\]

  所以时间复杂度就为O(n)了。

  相应的代码就通过一道模板题来给出吧。

 

786. 第k个数

给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整数数列。

输出格式

输出一个整数,表示数列的第 k 小数。

数据范围

1≤n≤100000,
1≤k≤n

输入样例:

5 3
2 4 1 5 3

输出样例:

3

   AC代码如下:

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int solve(int *a, int left, int right, int k) {
 6     if (left == right) return a[left];      // left == right,说明只有一个数字,这个数字就是我们要找到的第k个数
 7     int x = a[left + right >> 1], i = left - 1, j = right + 1;
 8     while (i < j) {
 9         while (a[++i] < x);
10         while (a[--j] > x);
11         if (i < j) swap(a[i], a[j]);
12     }
13     
14     int leftNum = j - left + 1;
15     if (k <= leftNum) return solve(a, left, j, k);
16     else return solve(a, j + 1, right, k - leftNum);
17 }
18 
19 int main() {
20     int n, k;
21     scanf("%d %d", &n, &k);
22     int a[n];
23     for (int i = 0; i < n; i++) {
24         scanf("%d", a + i);
25     }
26     printf("%d", solve(a, 0, n - 1, k));
27     
28     return 0;
29 }

 

参考资料

  AcWing 786. 第k个数:https://www.acwing.com/video/228/

这篇关于快速选择算法(找到第k个数字)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!