【摩尔投票法】leetcode 主要元素

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5

示例 2：

输入：[3,2]
输出：-1

示例 3：

输入：[2,2,1,1,1,2,2]
输出：2

说明：
你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-majority-element-lcci

思路一

排序，然后遍历数组，设数组长度为n，假如有一个元素连续出现超过n/2次，那么这个元素就是主要元素，由于使用快排，时间复杂度O(nlogn)，空间复杂度O(1)。

public int majorityElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    if (nums.length == 1) {
        return nums[0];
    }

    Arrays.sort(nums);

    // 当前重复次数
    int count = 1;

    for (int i = 1; i < nums.length; i++) {
        count = (nums[i] == nums[i - 1]) ? count + 1 : count;
        if (count > nums.length / 2) {
            return nums[i];
        }
    }
    return -1;
}

思路二

使用摩尔投票法，时间复杂度O(n)，空间复杂度O(1)

算法思想

摩尔投票法的核心思想是抵消，如果两个数字不同，就互相抵消，抵消到最后，肯定会剩下一个或多个相同的数字，这里有两种情况：
1.剩下的这个数字就是主要元素，因为它的数量超过了其他所有数字的数量和，就算其他所有数字都和它抵消，也抵消不完，更何况其他数字也会互相抵消；
2.数组不存在主要元素，比如1 2 1 2 3这个例子，1和2互相抵消，最后剩下3。

算法实现

public int majorityElement(int[] nums) {
    // 主要元素的候选人
    int major = nums[0];
    // major的计数器，即major的数量
    int count = 1;

    for (int i = 1; i < nums.length; i++) {
        // count为0，说明前面的互相抵消完了
        if (count == 0) {
            // 重新选择候选人
            major = nums[i];
            count = 1;
        } else {
            // 如果当前元素与候选人相同，则count+1，否则count-1，表示候选人被抵消掉一个
            count = (major == nums[i] ? count + 1 : count - 1);
        }
    }
    // count为0，说明不存在主要元素
    if (count == 0) {
        return -1;
    }
    // count不为0，不代表major就是主要元素，比如1 2 1 2 3这种情况
    // 所以还需要遍历数组，计算major的出现次数，判断是否大于数组一半
    count = 0;
    int half = nums.length / 2;
    for (int i = 0; i < nums.length; i++) {
        count = nums[i] == major ? count + 1 : count;
        if (count > half) {
            return major;
        }
    }
    return -1;
}