用头脑风暴学算法，对于一个问题，我们不只是要解决它，还要去思考有什么好的方法，差的方法去解决，甚至是一些错误的但可以提供思想借鉴的方法。

此问题“数组中出现次数超过一半的数字”是一道非常经典的算法题，我把它放在算法风暴系列第一篇来解析，探讨学习一个算法的过程，从慢到快，从最直观的方法到脑洞大开的方法，由表面深入本质。

下一篇：算法风暴之二—最小的k个数

问题描述

给定一个数组，且已知数组中有一个数出现次数超过一半（严格），请求出这个数。

问题很简单，方法也多样，但什么方法是最好的呢？为什么它最好？各种方法之间有什么优缺点？下面我们一一展开。

方法一：给数组排序

这大概是最直观的方法了，最容易想到，也是最多人能够想出来的。如果我们使用快排的话，只需要O(nlogn)的时间就可以找到这个数。

那么思考这样一个问题：给数组排序了，然后怎么找这个数呢？有两种方法

1、从小到大遍历已排序数组，同时统计每个数出现的次数（某个数和上一个数不同则计数置为1），如果出现某个计数超过一半，那么正在计数的数就是所求数。

PS：这种方法可行，相比于快排的时间复杂度是可以忽略的，但是我们还有更好的方法，直击本质。

2、对一个已排好序的序列，出现次数超过一半的数必定是中位数。因此，我们只要输出中位数即可。

复杂度分析：

时间复杂度 O(nlogn)
空间复杂度 O(n)

手写快排代码：

 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

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#define RAND(start, end) start+(int)(end-start+1)*rand()/(RAND_MAX+1);
using namespace std;

const int maxn = 10005;

int Partition(int *data, int length, int start, int end)
{
	if (start == end) return start;
	srand((unsigned)time(NULL));
	int index = RAND(start, end);
	swap(data[index], data[end]);
	int one = start - 1;
	for (index = start; index < end; ++index) {
		if (data[index] < data[end]) {
			++one;
			if (one != index) swap(data[one], data[index]);
		}
	}
	++one;
	swap(data[one], data[end]);
	return one;
}

void QuickSort(int *data, int length, int start, int end)
{
	if (length <= 1) return;
	int mid = Partition(data, length, start, end);
	if (mid > start)
		QuickSort(data, length, start, mid - 1);
	if (mid < end)
		QuickSort(data, length, mid + 1, end);
}

int main()
{
	int n, data[maxn];
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> data[i];
	}
	QuickSort(data, n, 0, n - 1);
	cout << data[n >> 1];
}

方法二：桶排序计数

如果我们需要统计的数组元素都是正整数呢？那么我们就可以使用桶排序，给他们计数，然后超过数组大小一半的就是结果了。

然而桶排序看上去很简单，“复杂度也不高”，却有很多的限制。

1、首先，数组统计的数需得是可hash的，不然无法将他们在hash数组上计数。但是某些情况，如元素有负值，可进行灵活转化，使其可hash。 2、其次，桶排序方法空间换时间，需要消耗额外的空间，取决于数据的范围。 3、桶排序并非真的那么快。桶排序的时间复杂度并非是普通的O(n), 它的n指的是最大数据范围，如果有这样一组数据1 100 10000 1000000，那么桶排序将会有至少1000000次循环，且开出1e6的空间，大大浪费资源。

桶排序方法适合数据范围不大，且数据密度较大的数据。非也，则在此问题上算不上好方法。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
using namespace std;

int main()
{
	int n, max_size = 0, ans = 0;
	cin >> n;
	int *data = new int[n];
	for (int i = 0; i < n; ++i) {
		cin >> data[i];
		max_size = max(max_size, data[i]);
	}
	int *hash = new int[max_size + 1];
	for (int i = 0; i <= max_size; ++i)
		hash[i] = 0;
	for (int i = 0; i < n; ++i)
		hash[data[i]]++;
	for (int i = 0; i <= max_size; ++i)
		if (hash[i] > n >> 1) ans = i;
	cout << ans;
	delete [] data;
	delete [] hash;
}

方法三：巧用栈

其实我们可以发现，上面的方法一和方法二，固然是这道题的解法之一，但不是非常具有针对性。也就是说，那两种方法是功能过剩的，而这所谓功能过剩，也正是导致它性能不是最佳的原因。

那么，我们就应该思考某种算法，只针对这个问题，完全的利用好效率。那么就要从题目出发，找蕴含在问题中的本质规律了。

其实这个问题的核心就是：出现次数超过一半。

我们做这样的思考：

假设k就是我们要求的那个数，那么对这个数组，删掉其中任意两个数所剩下的数组，其对应的k值会改变吗？答案是会的。但是，如果删掉任意两个不相同的数呢？答案是不会！ 为什么不会？相信聪明的读者瞬间就明白原因，只需进行简单的推导就可以了。

具体的实现过程就是：每遍历一个数，就将其入栈，同时查询它和栈内前一个元素的大小，如果不同，就同时出栈，否则不变。

以上，就是用栈的方法解决这个问题的核心。

时间复杂度 O(n)
空间复杂度 O(n)

栈实现代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int *data = new int[n];
	int *stack = new int[n];
	int top = 0;
	cin >> data[0];
	stack[++top] = data[0];
	for (int i = 1; i < n; ++i) {
		cin >> data[i];
		stack[++top] = data[i];
		if (top > 1 && stack[top] != stack[top - 1]) top -= 2;
	}
	cout << stack[top];
	delete [] data;
	delete [] stack;
}

方法四：找中位数（第n/2大数）

从方法一的分析中我们知道，这个数组的中位数就是答案。方法一是通过给所有的数进行排序找出这个中位数，而我们思考，排序是否有些大材小用？找这个中位数的方法是否可以更简单些？

答案是有的，而且这类问题被称为找第k个数。

思想是快排的思想。时间复杂度为O(n)

利用快排思想，我们可以找出第n/2大的数，同时在第n/2th数左边的数都小于它，右边的数都大于它。这个数就是数组的中位数。

快速排序简称快排，利用分治的思想，在数组中随机选择一个数，然后以这个数为基准，把大于它的数划分到它的右侧，小于它的数划分到它的左侧，并且递归的分别对左右两侧数据进行处理，直到所有的区间都按照这样的规律划分好。

那么在这个问题中，如何利用快排的方法呢？快排是对每一个区间进行分治处理，而此问题不必，我们只要找到第n/2小的数。每次随机划分得的第m个数，如果m < n/2, 那么对[m + 1, n - 1]这个区间继续递归；如果m > n/2，那么对[0, m - 1]这个区间进行递归；如果刚好有m = n/2，那么函数结束，区间[0, n/2 - 1]的数就是最小的n/2个数。

此算法的平均时间复杂度为O(n), 快速排序的详细证明可参考“算法导论”。

 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 <iostream>
#include <cstdlib>
#include <ctime>
#define RAND(start, end) start + (int)(end - start + 1)*(rand()/(RAND_MAX + 1))
using namespace std;

int Partition(int *data, int length, int start, int end)
{
	if (start == end) return start;
	srand((unsigned)time(NULL));
	int index = RAND(start, end);
	swap(data[index], data[end]);
	int one = start - 1;
	for (index = start; index < end; ++index) {
		if (data[index] < data[end]) {
			++one;
			if (one != index) swap(data[one], data[index]);
		}
	}
	++one;
	swap(data[one], data[end]);
	return one;
}

void FindIt(int *data, int length, int start, int end)
{
	int mid = Partition(data, length, start, end);
	if (mid == length >> 1) return;
	else if (mid > length >> 1) FindIt(data, length, start, mid - 1);
	else FindIt(data, length, mid + 1, end);
}

int main()
{
	int n;
	cin >> n;
	int *data = new int[n];
	for (int i = 0; i < n; ++i) {
		cin >> data[i];
	}
	FindIt(data, n, 0, n - 1);
	cout << data[n >> 1];
}

下一篇：算法风暴之二—最小的k个数