找出出现次数超过一半的数字

hl同学问我一道这个题，想了一种方法，感觉还是不错的，只扫描一次，贴一下伪代码：

int more_than_half(int a[],int n){
	stack<int> st;
  	for(int i = 1; i < n; i++){
  		if(st.empty()){
      			st.push(a[i]);
  		}else{
      			if(a[i] != st.top()){
       				st.pop();
      			}else{
				st.push(a[i]);
      			}
  		}
	}
	return st.top();
}

 思想是不同的数相互抵消，最终剩的数就是超过一半的。

按照这种思想，计数的方法来实现：

int more_than_half(int a[],int n){
	int count,i;
	int res;
	for(i = count = 0; i < n; i++){
		if(count == 0){
			res = a[i];
			count = 1;
		}else{
			if(res == a[i])
				count++;
			else
				count--;
		}
	}
	return res;
}

评论

2 楼 fuliang 2010-05-29  

D04540214 写道

运行java代码时候，传进 int[] a = new int[] {1, 2, 1, 2, 1, 2,4}; 最 后 答 案 是 4.

这样的相互抵消好像不妥当

前提是有超过一半的数存在，才能找到。

1 楼 D04540214 2010-05-29  

运行java代码时候，传进 int[] a = new int[] {1, 2, 1, 2, 1, 2,4}; 最 后 答 案 是 4.

这样的相互抵消好像不妥当