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

╰+攻爆jí腚メ 2023-10-06 10:14 15阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关折半查找--减治法

折半查找–减治法 ‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬

r囧r小猫/ 2024年03月17日 09:53/ 0 赞/ 66 阅读

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

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

╰+攻爆jí腚メ/ 2023年10月06日 10:14/ 0 赞/ 16 阅读

相关回溯法装载问题java最优解,回溯法最优装载问题（java）

1.问题描述：有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船，其中集装箱 i 的重量为 w\[i\], 且重量之和小于(c1 + c2)。装载问题要

超、凢脫俗/ 2022年11月17日 03:58/ 0 赞/ 194 阅读

相关 postgresql 给表添加主键的最优方案

os: centos 7.6 db: postgresql 13 版本 cat /etc/centos-release CentOS Linux

我就是我/ 2022年08月31日 15:15/ 0 赞/ 508 阅读

相关最优服务次序问题

最优服务次序问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述设有n 个顾客同时等待一项

不念不忘少年蓝@/ 2022年08月10日 05:57/ 0 赞/ 172 阅读

相关减治法之插入排序（C实现）

include <stdio.h> void InsertSort(int A[]); int main() { int i, a

约定不等于承诺〃/ 2022年08月09日 18:51/ 0 赞/ 95 阅读

相关主元素问题

主元素定义如果A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称X是A的主元素。问题要求如果A中的元素是可以排序的，设计一个时间复杂度为O（

小灰灰/ 2022年07月16日 00:19/ 0 赞/ 200 阅读

相关 DP-求最大值求最优解

Description 分配了8个任务,时间不冲突的情况下,挣得工资最多 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

悠悠/ 2022年04月15日 07:08/ 0 赞/ 258 阅读

相关最优合并问题

最优合并问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定k 个排好序的序列s

深碍√TFBOYSˉ_/ 2022年02月16日 15:06/ 0 赞/ 185 阅读

相关最优合并问题

最优合并问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem

た入场券/ 2022年02月15日 04:25/ 0 赞/ 175 阅读