找主元

Java 动态规划

对给定的整数集，寻找主元，即寻找出现次数严格大于一半的元素。

方法介绍

选段首元素作为试验主元，计数=0作为起点，碰到段首元素则计数++，非段首元素则计数–，计数=0则段结束，选下一个为试验主元。 若段首是主元，则去掉了同样数量的主元和非主元；否则，若段首非主元，则去掉相同甚至更多数量的非主元， 故主元仍是剩下部分的主元，最后再加上验证，就是完整的算法。

代码实现

package fdmain;
public class Fdmain {
	public static void main(String args[]){
	int[] a = {2,2,3,1,2,1,1};

	int firstCount = 0; // 段首元素计数
	int firstElement = 0;  // 段首元素
	for( int e : a ) {
		if( firstCount == 0 ) // 新的一段
			firstElement = e;
		if( e == firstElement )
			firstCount ++;
		else
			firstCount --;
	}

	// 最后一段的段首元素即为候选，需要验证
	int count = 0;
	for( int e : a )
		if( e == firstElement )
			count ++;
		else
			count --;
	if( count > 0 )
		System.out.println( firstElement );
	else
		System.out.println( "无主元" );
}
}