topK 面试必问 SDUTOJ 4166 4228(数据加强) 第k小的数 堆排 快排 kth

缘起

topK问题都是大厂面试手写必问的. 遂找到1道模板题 sdutoj 4166 第k小的数 和这道题的数据加强版 sdutoj 4228 第k小的数 进行练习.

分析

4166题目是中文的

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
Problem Description
现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较快
的方式找出该序列的第k小数并输出。

Input
多组输入。
首先输入一个数据组数T（1<=T<=100）
接下来是T组数据。
每组数据有两行。
第一行先输入两个整数，n和k。
接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。

Output
对于每组数据，输出该组数据中第k小的数num。

Sample Input
1
6 4
3 2 5 1 4 6

Sample Output
4

限制
Time Limit: 5000 ms 
Memory Limit: 65536 KiB

4228题目也是中文的

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
Problem Description
现有一个包含n个整数（1<=n<=20000000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较
快的方式找出该序列的第k小数并输出。

Input
多组输入。(代表输入只有一个T)
首先输入一个数据组数T（1<=T<=100）
接下来是T组数据。
每组数据有两行。
第一行先输入两个整数，n和k。
接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。

Output
对于每组数据，输出该组数据中第k小的数num。

Sample Input
1
6 4
3 2 5 1 4 6
Sample Output
4

限制
Time Limit: 3000 ms 
Memory Limit: 65536 KiB

首先处理 4166

方法1: 排序之后，你懂的， 复杂度是 O(nlogn)

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
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;

//#define LOCAL

int n,k, a[90000005];

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n,&k);
		for (int i = 0; i<n; i++) scanf("%d", a+i);
		sort(a, a+n);
		printf("%d\n", a[k-1]);
	}
	return 0;
}

ac情况

6496355 yfs 4166 Accepted 32 ms 184 KiB g++ 389 B 2019-08-14 16:51:34

但是4228用上述代码就吃T了——因为快排性能最坏也会到 O(n^2) 去. 所以改用shell排序

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
#include "stdafx.h"

#include <stdio.h>

#define LOCAL

int n,k, a[20000005];

void shell()
{
	int gap = n;
	do 
	{
		gap = gap/3+1;
		for (int i = gap; i<n;i++) // [gap, n) 内的数变化
		{
			int j = i, t = a[i]; // 为 a[i]找新家
			while(j>=gap && a[j-gap]>t)
			{
				a[j] = a[j-gap];
				j-=gap;
			}
			a[j] = t;
		}
	} while (gap>1);
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n,&k);
		for (int i = 0; i<n; i++) scanf("%d", a+i);
		shell();
		printf("%d\n", a[k-1]);
	}
	return 0;
}

但是还是超时~ （但是提交4166的话可以ac，略慢——40ms）

其实如果状态取值有限的话，则可以使用桶排序，但是此题显然不适合. 因为取值空间太大.

方法2: 进行k轮冒泡. 复杂度是O(k*n), 这个方法就不展示了，肯定要吃T的.

方法3: 堆排, 复杂度O(nlogk) 构建大根堆

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
#include "stdafx.h"

#include <stdio.h>

#define LOCAL

int n,k, a[20000005];

inline void swap(int &a, int &b)
{
	a = a^b;
	b = a^b;
	a = a^b;
}

struct Heap
{
	int *heapArray,n; // 堆数组（索引0不用于存储数据）, n是堆数组中数字的实际个数
	Heap(int *a, int n):heapArray(a),n(n) // 建堆
	{
		for (int i = (n>>1); i; i--)
		{
			siftdown(i);
		}
	}

	void siftdown(int index)
	{
		while((index<<1)<=n) // 如果还有左孩子
		{
			int t = index, lc = (index<<1), rc = (index<<1)|1; // 左右孩子
			if (heapArray[index] < heapArray[lc])
			{
				t = lc;
			} // 和左孩子预交换
			if (rc<=n && heapArray[rc]>heapArray[t]) // 如果有右孩子并且右孩子更大
			{
				swap(heapArray[index], heapArray[rc]); // 则index真正应该和右孩子交换
				index = rc; // 跳到右孩子去
			}
			else if (t!=index) // 说明要和左孩子交换
			{
				swap(heapArray[index], heapArray[t]); // 和左孩子交换
				index = t; // 跳到左孩子去
			}
			else
			{
				return; // 既不和左孩子,也不和右孩子交换, heapArray[index]的调整已经完成
			}
		}
	}
};

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n,&k);
		for (int i = 1; i<=n; i++) scanf("%d", a+i);
		Heap heap(a,k); // 使用 a[1,...,k]建立大根堆（即堆顶是堆数组中最大的元素）
		for (int i = k+1; i<=n;i++)
		{
			if (a[i]>heap.heapArray[1]) continue;
			heap.heapArray[1] = a[i];
			heap.siftdown(1);
		}
		printf("%d\n", heap.heapArray[1]);
	}
	return 0;
}

依旧只能过 4166, 而4228依旧被卡

方法4: 快排

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
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n ,k,a[20000005];

void qsort(int lb, int ub, int k) // 求[lb, ub]上的第k小
{
	if (lb>ub)return;
	int pivot = a[lb];
	int i = lb,j = ub;
	while(i<j)
	{
		while(i<j && a[j]>=pivot)j--; // 找到从右至左第一个违规的
		while(i<j && a[i]<=pivot)i++; // 找到从左至右第一个违规的
		if (i<j) swap(a[i],a[j]); // 则 a[i]<pivot
	}
	a[lb] = a[i];
	a[i] = pivot; // i处的pivot将[lb,ub] 分成2半
	if (i==lb+k-1) // 如果 a[i]就是第k大
	{
		printf("%d\n", a[i]);
		return;
	}
	// 如果a[i]不是第k大，递归处理
	i>lb+k-1?qsort(lb, i-1, k):qsort(i+1,ub,lb+k-i-1);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n,&k);
		for (int i = 0; i<n;i++) scanf("%d", a+i);
		qsort(0, n-1, k);
	}
	return 0;
}

但是也只能ac掉 4166, 而4228 依旧会T掉, 就算随机化轴点pivot取值也依旧T

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
#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
#define LOCAL

int n ,k,a[20000005];

void qsort(int lb, int ub, int k) // 求[lb, ub]上的第k小
{
	if (lb>ub)return;
	swap(a[lb], a[ub]);
	int pivot = a[lb];
	int i = lb,j = ub;
	while(i<j)
	{
		while(i<j && a[j]>=pivot)j--; // 找到从右至左第一个违规的
		while(i<j && a[i]<=pivot)i++; // 找到从左至右第一个违规的
		if (i<j) swap(a[i],a[j]); // 则 a[i]<pivot
	}
	a[lb] = a[i];
	a[i] = pivot; // i处的pivot将[lb,ub] 分成2半
	if (i==lb+k-1) // 如果 a[i]就是第k大
	{
		printf("%d\n", a[i]);
		return;
	}
	// 如果a[i]不是第k大
	i>lb+k-1?qsort(lb, i-1, k):qsort(i+1,ub,lb+k-i-1);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n,&k);
		for (int i = 0; i<n;i++) scanf("%d", a+i);
		qsort(0, n-1, k);
	}
	return 0;
}

最后可以使用c++的stl nth_element

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
#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
#define LOCAL

int n ,k,a[20000005];


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n,&k);
		for (int i = 0; i<n;i++) scanf("%d", a+i);
		nth_element(a, a+k-1,a+n);
		printf("%d\n", a[k-1]);
	}
	return 0;
}

4116是ac的，但是4228 爆了内存.

所以本文给出了topK问题的四种常规（全部ac掉sdut oj 4166）

  1. 排序（不论是快排还是桶排还是shell）
  2. 堆排
  3. 快排
  4. k轮冒泡
  5. 使用 nth_element

但是本文证明了，只能应对数据量较小的情况——10w级别的没问题，但是1000w级别的就嗝屁了~

至于 1000w级别如何处理，后面我写文章处理. 本文依旧有收获——至少面试BAT之类，如果问到手写topK是妥妥的不怕的^_^.