减治：主元素问题的最优解

╰+攻爆jí腚メ 2023-10-06 10:14 32阅读 0赞

## 减治：主元素问题的最优解 ##

#### 主元素问题： ####

设A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称x是A的主元素。给出一个算法，判断A中是否存在主元素并输出

#### 最优解思路： ####

利用了减治的思想，移出两个不同的数字，剩下数字构成的集合主元素不改变

主元素出现的次数>n/2 ，若两个不同的元素两两相抵消，最后若数组元素完全抵消，则不存在主元素，若没有完全抵消，则余下的元素可能为主元素（是否为主元素还需要进行检验，如（0,1,2）虽然剩下2，但并不存在主元素）

首先设C=A\[0\]，计数值count=1，

从第二个元素开始扫描，若元素和C相同，则不需消除，计数值count加1，即现在有2个相同的数准备着与不同值相消

若元素不与C相同，若count>0，进行消去，count减1;  
若count=0，即刚刚进行过消去，现在已没有为相消储备的元素，当前元素变为相消储备元素，count=1

若扫描完毕后，count=0，证明元素完全抵消，返回-1；  
否则再对数组进行一次扫描，统计C值出现的次数，若大于数组长度的一半，则输出C

#### 代码： ####

int search_main( int* A,int n )
    {
        
    	int c=A[0];
    	int count=1;
    	int i;
    	for( i=1;i<n;i++ )
    	{
        
    		if( A[i]==c )
    		{
        
    			count++;
    		}
    		else
    		{
        	
    			if( count>0 )
    				count--;
    			else
    			{
        
    				c=A[i];
    				count=1;
    			}
    		}
    	}
    	if(count>0)
    		for( i=0,count=0;i<n;i++ )
    		{
        
    			if( c==A[i] )
    			{
        
    				count++;
    			}
    		}
    	if( count>n/2 )
    		return c;
    	else
    		return -1;
    }