题目

描述

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。

样例

给出数组[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);
        }
    }
}