Majority Element
今天是一到有关数学计算的题目，较为简单，来自LeetCode，难度为Easy，Acceptance为37.5%。
题目如下
Given an array of size n, find the majority element. The majority element is the element that appears more than
n/2times.
You may assume that the array is non-empty and the majority element always exist in the array.
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
该题的思路较为简单，因为有一个数的出现次数超过了1/2，那么可以得出，其余所有的数字加起来也不到1/2。
利用这个性质，我们可以遍历整个数组，然后让不同的数字相互抵消就可得到最后的结果，具体过程如下：
在遍历的过程中，用一个变量major记录出现次数最多的数字，用另一个变量count记录该数字的出现次数；当遍历每一个数字时，首先比较与major是否相同，若相同则count加一，若不同则count减一，当count减到0时，则将出现最多的数字设为major；则在遍历的最后剩下的数字即为次数最多的数字。
下面我们来看具体代码
代码如下
java版
public class Solution {
public int majorityElement(int[] num) {
int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--;
}
return major;
}
}
c++版
int majorityElement(vector<int> &num) {
int majorityIndex = 0;
for (int count = 1, i = 1; i < num.size(); i++) {
num[majorityIndex] == num[i] ? count++ : count--;
if (count == 0) {
majorityIndex = i;
count = 1;
}
}
return num[majorityIndex];
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
image
