首页 > 代码库 > 关于水王的题目——找到出现次数大于/等于数组长度一半的数

关于水王的题目——找到出现次数大于/等于数组长度一半的数

关于水王的题目——找到出现次数大于/等于数组长度一半的数

    

1. 题目描述


    一个长度为n的数组,里面有一些数出现的次数比较多。请找到出现次数大于数组长度一半的数。(水王1)


   一个长度为n的数组,里面有一些数出现的次数比较多。请找到出现次数等于数组长度一半的数。(水王2)



2. 双变量法和三变量法


    不管是水王1,还是水王2,解法的时间复杂度都是O(n)。


    对于水王1,我们用两个变量来解决:candidate and count,前者记录水王的候选者,后者次数他的绝对次数!注意,这里是绝对次数~下面我们来说说具体做法吧:


  • 将candidate=a[0], count=1, 遍历后面的数;
  • 如果后面一个数等于candidate,那么count++; 
  • 如果后面一个数不等于candidate, 那么count--; 
  • 当count==0的时候,我们让candidate等于下一个数,此时前面的数达到了“平衡”~而绝对次数的实际意义就是统计这些数中出现candidate和不是candidate的个数之差!
  • 输出最后让count!=0的那个candidate,记为水王~


    这一步显然可以想到,绝对次数>0的一定就是水王了。


代码如下:


#include<iostream>
using namespace std; 

int findShuiWang(int *a, int num)
{
	int candidate=a[0]; 
	int count=1; 

	for(int i=1; i<num; i++)
	{
		if(candidate==a[i])
			count++; 
		else
		{
			count--; 
			if(count==0)
			{
				candidate=a[i+1]; 
				i++; 
				count=1; 
			}
		}
	}
	return candidate; 
}

int main()
{
	int a[6]={2, 1, 2, 2, 1, 2}; 
	int num=6; 

	int shuiWang; 
	shuiWang=findShuiWang(a, num); 
	cout<<shuiWang<<endl; 

	return 0; 
}


    对于水王2,其出现的次数恰好等于数组长度的一半,这个时候我们可以确定两件事情:

    1)水王的“绝对次数”==0; 

    2)数组的长度一定是个偶数。


    同样我们的解法答题按照上面水王1的思路来,一直到最后candidate的count==0,此时要么这个candidate就是水王2,要么就是数组的最后一个数,因为是他才让candidate的count变成0的,到了二选一的节奏了~

    此时,我们巧妙的再引入一个变量help,记录数组最后一个数出现的次数,如果等于n/2(注意n一定是偶数),那么我们就认为最后一个数是水王,否则就是candidate是水王~


    程序如下:

#include<iostream>
using namespace std; 

int findShuiWang(int *a, int num)
{
	int candidate=a[0]; 
	int count=1; 
	int lastOne=a[num-1]; 
	int helpCount=lastOne==a[0] ? 1 : 0; 

	for(int i=1; i<num-1; i++)  //a trick to avoid overflow
	{
		if(candidate==a[i])
			count++; 
		else
		{
			count--; 
			if(count==0)
			{
				candidate=a[i+1]; 
				i++; 
				count=1; 
			}
		}
		
		if(a[i]==lastOne)
			helpCount++; 
	}
	return helpCount==num/2-1 ? lastOne : candidate;   //the last one must be lastOne!
}

int main()
{
	int a[6]={2, 1, 2, 2, 1, 0}; 
	int num=6; 

	int shuiWang; 
	shuiWang=findShuiWang(a, num); 
	cout<<shuiWang<<endl; 

	return 0; 
}


关于水王的题目——找到出现次数大于/等于数组长度一半的数