区间K大数查询

问题:在一个无序序列中,查找给定区间中的第K大的数

这是一个很经典的问题,但是之前并没有深究,最近刷题的时候碰到了,就来总结一波……

Method 1:先排序,然后直接找到第K大的数

这种方法最常规、最易想到且没有限制条件;但是效率比较低,时间复杂度为O(n*log n),采用高效率的排序算法

若采用某些效率比较高的排序算法,例如快速排序算法、堆排序算法,其时间复杂度均为O(n*log n)

Method 2:进行K次线性扫描

这种方法的前提条件是K不是太大;时间复杂度为O(k*n)

具体做法是:进行每一次扫描的过程中,找到当前最大的数,并把它从序列中移出,这样扫描K次,就可以找到第K大的数了…… 例如:第一次扫描,找到最大的数,然后把它移出这个序列;然后进行第二次扫描,找到最大的数,这就是第2大的数字,移出这个序列;第三次扫描……

(当然,也可以只扫描一遍,然后记录下第K大的数字。同样K很小的前提下可以这样做……)

Method 3:用空间换时间

这种方法的前提条件是序列中的所有值非负、且最大值不能太大

具体做法是:开一个数组,数组长度为可能出现的最大值,初值赋为0,表示出现的次数均为0次;然后根据序列,依次统计每一个数出现的次数(例如:序列为23,1,4,50,4;则arr[1] = 1, arr[4] = 2, arr[23] = 1, arr[50] = 1, 其余的均为0)

查找第K大的数时,从最大的、数组值非0的数开始找起,逆向查找、并进行累加计数,当计数>=K时,就找到第K大的数了

Method 4:利用快速排序原理(重点掌握并理解算法思想)

快排的原理:利用快速排序将无序序列转换为有序序列的过程中,经过多次的划分;(这里假定进行降序排列)在每一次的划分中,在序列中找到一个枢轴(pivot),划分的结果是 pivot 左边的数均比它大,右边的数均比它小;然后对子序列进行同样的操作,递归进行、直到所有子序列有序为止。

改造:我们的目标是找到第K大的数,若在一次划分之后、pivot左边的数(加上它本身)共有K个,那么pivot位置上的数就是我们要找的第K大的数;其一:我们不必要求前K-1大的数有序,所以不必继续进行递归划分;其二:每一次的划分都将原序列分为左、右两个子序列,快排算法需要对这两个子序列都继续进行递归的划分,而在这里我们只需要根据情况(具体看算法步骤)选择一个子序列继续划分即可;因此这种求第K大的数算法的时间复杂度小于快速排序的复杂度,为O(n*logK)

算法步骤:经过一次划分(partition)之后,枢轴pivot将原序列划分为两个部分:S和T [即原序列变为(S T)、pivot包含在子序列S中、注意使用降序排序],会出现下列三种情况:

  1. 子序列S中有K个数,此时pivot位置即为第K大的数,算法结束
  2. 子序列S中的数字个数小于K,假设个数为L,则需要子序列T中继续递归划分出来前(K-L)个数
  3. 子序列S中的数字个数大于K,则需要子序列S中继续递归划分出来前K个数

下面来看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
快速排序的一次划分
过程不懂的翻数据结构课本……
*/
int my_partition(int a[], int low, int high) {
int i = low, j = high, x = a[low];
while (i < j) {
while (i<j && a[j]<=x) j--;
a[i] = a[j];
while (i<j && a[i]>=x) i++;
a[j] = a[i];
}
a[i] = x;
return i;
}
/*
降序排序
当一次划分之后、pivot左边的数(包括它本身)恰为k个时,停止划分
*/
void find_kmax(int a[], int low, int high, int k) {
if (low < high) {
int poi = my_partition(a, low, high);// 得到一次划分之后 pivot的位置
int len = poi - low + 1;// 计算子序列S的长度
if (len < k) {// 情况2
find_kmax(a, poi + 1, high, k - len);
} else if (len > k) {// 情况3
find_kmax(a, low, poi - 1, k);
}
}
}
int main() {
int arr[] = {23, 50, 500, 4, 100, 300, 200, 99, 400};
int len = sizeof(arr) / sizeof(int);// 求数组长度
int l, r, k;// 区间为[l, r],从1开始
scanf("%d %d %d", &l, &r, &k);
int a[100];
memcpy(a, arr, sizeof(arr));// 将arr数组的元素copy到a数组中,这么做是为了避免破坏原数组、能够进行多次不同区间的查询
find_kmax(a, l-1, r-1, k);// 注意区间下标与数组下标的转换
printf("%d\n", a[l-1 + k-1]);// 注意第k大的数在数组a中的位置!
return 0;
}

tips:这里我们求了第K大的数,若需要求_前_K大的数,直接把数组a[l-1]~a[l-1 + k-1]共K个数输出即可;当然了,里面的元素序列不一定是完全有序的。

Method 5:利用堆排序的原理(掌握并理解其思想)

我们的目标是寻找第K大的数,相应地,这种方法的原理就是 维护一个具有K个元素的小顶堆(最小堆),堆顶元素即为我们寻找的第K大的数。实际应用中 并没有上述利用快速排序思想算法的效率高,时间复杂度同样为O(n*log K)

具体的算法步骤:

  1. 把原序列给定的区间前K个数放入小顶堆中,进行初始建堆的过程
  2. 然后把区间中剩余的数字依次和堆顶比较,若比堆顶元素大、则替换堆顶,并重新维护堆的结构

下面来看具体的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
小顶堆:筛选过程的子过程
对当前的i结点进行调整,保证i结点的值<=其左右孩子的值
然后对其左右孩子进行同样的操作……(递归进行)
这也是需要逆向筛选(由最后一个非终端结点到根结点)的原因
*/
void adjust_loop(int *heap, int i, int len) {
if (i < len) {// 因为用的是数组heap来保存堆,这里的作用是判断是否出界
int l = 2 * i + 1, r = 2 * i + 2;// i结点的左右孩子
if (r < len && heap[r] < heap[i]) {// 如果存在右孩子且i结点的值小于~
int tmp = heap[i];
heap[i] = heap[r];
heap[r] = tmp;
adjust_loop(heap, r, len);// 继续筛选调整右孩子
}
if (l < len && heap[l] < heap[i]) {// 如果存在左孩子且i结点的值小于~
int tmp = heap[i];
heap[i] = heap[l];
heap[l] = tmp;
adjust_loop(heap, l, len);// 继续筛选调整左孩子
}
}
}
/*
小顶堆:筛选过程
从最后一个非终端结点开始进行筛选,直到根结点
*/
void heap_adjust(int *heap, int len) {
for (int i = (len-1)/2; i >= 0; i--) {
adjust_loop(heap, i, len);
}
}
/*
完成建立一个小顶堆的过程
即此函数的目标是 把最大的K个数放入一个小顶堆中,堆顶即为第K大的数
*/
void find_kmax(int arr[], int l, int r, int k, int *heap) {
// 区间[l, r]中的前k个元素先建堆
for (int i = l; i < k+l; i++) {
heap[i-l] = arr[i];
}
heap_adjust(heap, k);
// 剩余的(r-l+1)-k个元素进行更新
for (int j = k+l; j <= r; j++) {
// 比堆中最小的值还要大,可以插入堆中
// (因为我们要找到前k大的数进入堆中)
if (arr[j] > heap[0]) {
heap[0] = arr[j];
heap_adjust(heap, k);
}
}
}
int main() {
int arr[] = {23, 50, 500, 4, 100, 300, 200, 99, 400};
int len = sizeof(arr) / sizeof(int);// 求数组的长度
int l, r, k;// 区间为[l, r],从1开始
scanf("%d %d %d", &l, &r, &k);
int *heap = new int[k];
find_kmax(arr, l-1, r-1, k, heap);// 注意区间下标与数组下标的转换
printf("%d\n", heap[0]);// 建立的是小顶堆,堆顶即为第k大的元素
delete heap;
return 0;
}

tips:同样,若需要求_前_K大的数,直接把这个小顶堆输出即可;当然,里面的元素序列不一定是完全有序的。

-------------本文结束  感谢您的阅读-------------