面试题29:数组中出现次数超过一半的数字

题目:数组中有一个数字出现的次数超过了数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2出现了5此,超过了数组的一半,因此输出2.


分析

  • 最直观的解决办法就是将数组排序,然后取其中位数即可。但排序最快也需要O(nlgn)的时间复杂度,效率不是特别高。代码略。

  • 还可以基于快速排序中的partition函数来求解。partition函数每次能确定一个值在数组中的确切位置。因此在找到位于数组中间位置的数字即可停止。 代码如下:

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
template<typename t="">
int Partition(vector<t>&amp; v,int left,int right)
{
int i=left,j=right-1;
T tmp=v[left];
while(i&lt;j)
{
while(i&lt;j &amp;&amp; v[i]&lt;=tmp)
i++;
swap(v[i],v[j]);
while(i<j vj="">=tmp)
j--;
swap(v[i],v[j]);
}
return i;
}
template<typename t="">
T _MoreThanHalfNum(vector<t>&amp; v,int left,int right)throw (NoNumIsMoreThanHalf)
{
int mid=Partition(v,left,right);
if(mid==v.size()/2)
{
if(CheckNumIsMoreThanHalf(v,mid))
return v[mid];
else
throw NoNumIsMoreThanHalf();
}
else if(mid&lt;v.size()/2)
return _MoreThanHalfNum(v,mid+1,right);
else
return _MoreThanHalfNum(v,left,mid);
}
template<typename t="">
T MoreThanHalfNum(vector<t>&amp; v)
{
_MoreThanHalfNum(v,0,v.size());
}
</t></typename></t></typename></j></t></typename>

  • 最优的方法是设置两个数字num和time,num表示数组中的某一个数字,time代表num出现的次数。我们可以从前往后遍历数组,如果当前值等于num,就给time++;如果不等于,就time–;当time减少到0时,用下一个数字替换num的值。这样下来,只需要遍历一遍数组,就可以找出出现次数超过一半的数字。 代码如下:

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
template<typename t="">
T MoreThanHalfNum(const vector<t>&amp; v)
{
if(v.size()==0)
throw NoNumIsMoreThanHalf();
T num=v[0];
int time=1;
int i;
for(i=1;i<v.sizei iftime="">0)
{
if(v[i]==num)
{
time++;
}
else
{
time--;
}
}
else
{
num=v[i];
time=1;
}
}
if(CheckNumIsMoreThanHalf(v,num))
return num;
else
throw NoNumIsMoreThanHalf();
}
</v.sizei></t></typename>

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>