leetCode 169 [PHP代码]

浏览数：177 / 时间：2015年06月09日

Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.

You may assume that the array is non-empty and the majority element always exist in the array.

寻找多数元素
就是某一个数组中的元素的个数是N ，这个N 大于数组个数/2 取整的值就是多数元素。

下面是PHP的代码实现。

// array(1,2,3,2,5,69,8,2,5,2)
// array(1,2,5,8,5,5,5,98,65,5,5)
// array(1,2,6,8,6,6,6,98,65,6,6)
echo majority(array(2,2,3,2,2,68,8,2,5,2));

function majority($n) {
print_r($n);echo "<br />";
	$elem = 0;
	$count = 0;
	// echo count($n);echo "<br />";
	for($i = 0; $i<count($n); $i++) {
		if($count == 0) {
			$elem = $n[$i];
			// print_r($elem);echo "<br />";
			$count = 1;
		}else{
		// print_r($n[$i]);echo "<br />";
			if($n[$i] == $elem) {
				$count++;
			}else{
				$count--;
			}
		}
	}
	if($count>0)
<span style="white-space:pre">	</span>return $elem;
<span style="white-space:pre">	</span>else
<span style="white-space:pre">	</span>return "Don't have majority element<br />";
}

算法描述：
将计数器置为1，并把元素1保存下来，从元素2开始比对，逐个的比较元素。
如果被扫描的元素和保存下来的值（元素1）相等，计数器加一，不相等，减一。
所有的元素（从元素2到结尾）比较完成计数器大于0，则返回元素一，是多数元素。否则
把元素2存入临时变量，再比较元素3开始的整个数组。
这样依次比较完数组。
判断有无大数。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

leetCode 169 [PHP代码]