题目
描述
给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。
样例
给出数组[1,1,1,1,2,2,2]，返回 1
解答
思路
看到这个题目，第一反应是排序后取中间数，这没什么好说的。
这个题目的挑战是时间复杂度为O(n)，空间复杂度是O(1)。这个有点意思。
如果一个数组存在主元素，那么在数组中删除两个不同的数，对于主元素的地位是没有影响的。根据这个思路设计算法。
代码
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
/**
* count: 统计当前认为的主元素的数量
* seed: 当前认为的主元素
* n: 数组长度
**/
int count = 0, seed = nums.get(0), n = nums.size();
//从两头往中间循环
for(int i = 1; i<n/2; i++){
//若两数相等，主元素备选
if(nums.get(i) == nums.get(n-i)){
//若当前没有认为的主元素
if(count == 0){
//那么取当前数为主元素
seed = nums.get(i);
//统计加一
count++;
}
//若已有认为的主元素
else{
// 若与主元素相等，统计量加一
if(seed == nums.get(i)) count++;
// 若与主元素不等，统计量减一
// 这里如果减小到0了，可能会产生主元素切换
else count--;
}
}
}
//统计主元素出现的次数
for(int i = 0;i<n;i++){
if(nums.get(i) == seed){
count++;
}
}
//超过一半才被认为是主元素
if(count >= n/2){
return seed;
}
//提交了几次发现如果没超过一半需要返回最后的元素
else{
return nums.get(n-1);
}
}
}
