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

心已赠人 2022-08-06 01:22 194阅读 0赞

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

# 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; 
    }