主元素问题

什么是主元素问题?

已知一个数组的大小，并且其中存在一个数，出现的频率大于50%，则称其为该数组的主元素。用一个算法找出这个数，要求其时间复杂度尽可能低。

这是一个很简单的问题, 解决的方法有很多, 思考这样一道问题的意义不在于只是把它解决, 而是找出多种解决它的方法, 感受算法的神奇.

衡量一个算法优劣的一个非常重要的尺度是时间复杂度, 我们如何让计算机用最短的时间, 解决这个问题呢?

先排序(比较排序)后计数的方法

先排序后后比较, 这种方法是比较常规的思维. 排序之后将每个相同的元素计数, 再根据数量判断是哪一个元素

比较排序最快的平均时间复杂度是O(nlogn), 所以这个方法最快的时间按复杂度是O(nlogn)

**这种排序方式在所有方式中效率较低, 但它适合各种数据类型(如浮点型), 且在某些情况下空间复杂度比计数排序的方法小很多. **

还可以判断是否存在这样一个主元素.

代码比较简单且常规, 不写出(实际上用STL的sort()很简单, 但手写快排, 还是算了吧……)

一个简单优化

对于一个已经排序好了的序列, 其实不需要给每个元素计数.

因为它是主元素(>50%), 所以只要取中值就可以知道它是哪个(它的值).

计数排序的方法

计数排序也叫桶排序, 是一种非比较型排序.

时间复杂度位O(N) (N取决于数据范围)

鉴于计数排序对数据类型的限制很大, 所以比较各种排序方法的优劣时通常不把计数排序和快排这种比较排序相比较(事实上没有意义)

如果数据稀松或者范围很大, 计数排序将会非常浪费空间(空间复杂度非常大)

但在某些特定的条件下, 计数排序确实是一种时间复杂度位O(n)的排序算法如: 数据是1-1e6之间的整数

同样可以判断是否存在这样一个主元素

而使用计数排序的方法觉得这道题, 不需要排序, 事实上它可以看作计数排序的一个子过程

用STL中的nth_element()函数

刚认识nth_element()函数没几天, 写这个问题的时候突然觉得可以用这个函数解决主元素问题.

思路是:

对N个数的序列用nth_element()找到第N/2+1个元素的值. 这个值就是主元素的值

缺陷是:

无法判断是否存在主元素

这是奇数的情况:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


#include <iostream>
#include <algorithm>
#define N 7

using namespace std;

int main()
{
	int a[] = {1, 4, 3, 1, 1, 2, 1}; //N为奇数, 从0开始 
	nth_element(a, a + N/2, a + N);
	cout << a[N/2];
}

这是偶数的情况:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


#include <iostream>
#include <algorithm>
#define N 6 

using namespace std;

int main()
{
	int a[] = {1, 3, 1, 1, 2, 1}; //N为偶数, 从0开始 
	nth_element(a, a + N/2, a + N);
	cout << a[N/3];
}

时间复杂度为O(N) nth_element()是STL算法库中一种O(N)的单元素排序算法函数

豆瓣里一种巧妙地方法

最后介绍的是一种豆瓣网友分享的巧妙算法

其核心思想在于：对于这样一个数组，去除掉任意两个不相等的数，剩下的数中，主元素的出现频率仍然大于50%。

但又缺陷:

只能在确定存在主元素的序列中找到这个主元素. 即无法判断是否存在主元素

引自豆瓣: 解法：声明一个变量count = 0，声明一个常量size等于数组大小。假设该数组的第一个元素a(1)为主元素，让其与a(2)进行比较，若相同，则使变量count+1，若不同，则count-1。然后继续比较a(3)。以此类推。

当与a(n)比较后，count = -1时，将count重新归为0，并重新假设a(n+1)为主元素，并继续与a(n+2)作比较。

当count>=(size-m)/2时，此时假设的主元素a(m)即为实际的主元素。或遍历完整个数组后，当前假设的主元素为实际主元素。

这个算法的时间复杂度最大才O(N)，看书看到这一段时令我顿时拍案叫绝啊。其核心思想在于：对于这样一个数组，去除掉任意两个不相等的数，剩下的数中，主元素的出现频率仍然大于50%。而使用count来进行加减计数，当count=0时，必然是偶数个数与假设的主元素进行了比较，且其中有一半与假设数相同一半与假设数不同（当count=-1时，加上假设数的集合，也满足该条件）。

下面是我写的简单代码(可能又bug)

 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>
#define N 7

using namespace std;

int main()
{
//	int a[] = {1, 4, 3, 1, 1, 2, 1};
	int a[] = {1, 3, 4, 4, 5, 4, 4};
//	int a[] = {1 ,5 ,6 ,8 ,7 ,9 ,4 ,2 ,7 ,5 ,2 ,2 ,2 ,2};
	int cnt = 0, tmp = a[0];
	for(int i = 1; i < N; ++i) {
		if(tmp == a[i]) cnt++;
		else cnt--;
		if(cnt < 0) {
			tmp = a[i];
			cnt = 0;
		}
	}
	cout << "cnt == " << cnt << endl;
	if (cnt > 0) cout << tmp << endl; 
	else cout << "There is no such a number !\n";
}

###总而言之, 主元素问题是一种很简单的思维启发问题, 方法有很多, 可是你想到了最简单的方法吗?

主元素问题_奇妙的思维

Contents