首页 > 代码库 > 线性时间内确定T[0:n]是否有一个主元素
线性时间内确定T[0:n]是否有一个主元素
设T[0:n-1]是n 个元素的数组。对任一元素x，设S(x)={ i | T[i]=x}。当| S(x) |>n/2 时，称x 为T 的主元素。设计一个算法，确定T[0:n-1]是否有一个主元素。
算法描述如下：
a1 a2 a3 a4 … aj aj+1 … … an 首先取a1 存入m 中，计数器k 置为1。
然后让m 比较a1，a2…，如果与m 相同，则k 加1，如果不同，k 要减1。
这样执行下去， 可能会在比较完aj 时，k=0，这时从新取aj+1 存入m，k 置为1。
重复上述操作，知道比较完a[1:n]中所有元素。
这个过程结束后， k 有两种可能值：①k=0，②k>0。
当k=0 时，a[0:n-1]必无主元素。
当k>0 时，a[0:n-1]可能有主元素，也可能没有主元素。如果 a[0:n-1]有主元素，则m 的值必为主元素。显然再将m 与a[0:n-1]所有元素比较一遍，即可知m 是否为a[0:n-1]的主元素，即a[0:n-1] 是否有主元素。
算法如下：
Template<class T> void MainMember(T a[],int n) { int i,j,k,m; m=a[0];k=1;j=0; for(i=1;i<n;i++) { if(m==a[i]) k++; else k--; if(k==0) { i++; if(i>n) break;//a[0:n-1]中元素已比较完了，跳出 m=[i];
k=1; } } if(k==0) cout<<"数组a 中没有主元素!"<<endl; else { for(i=0;i<n;i++) if(m==a[i]) j++; } if(j>n/2) cout<<"数组a 中存在主元素,主元素为:"<<m<<endl; else cout<<"数组a 中没有主元素!"<<endl; }
线性时间内确定T[0:n]是否有一个主元素
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。