數(shù)組中占比超過一半的元素稱之為主要元素。給定一個整數(shù)數(shù)組，找到它的主要元素。若沒有，返回-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) 內(nèi)完成嗎？

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

思路一

排序，然后遍歷數(shù)組，設數(shù)組長度為n，假如有一個元素連續(xù)出現(xià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);

    // 當前重復次數(shù)
    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)

算法思想

摩爾投票法的核心思想是抵消，如果兩個數(shù)字不同，就互相抵消，抵消到最后，肯定會剩下一個或多個相同的數(shù)字，這里有兩種情況：
1.剩下的這個數(shù)字就是主要元素，因為它的數(shù)量超過了其他所有數(shù)字的數(shù)量和，就算其他所有數(shù)字都和它抵消，也抵消不完，更何況其他數(shù)字也會互相抵消；
2.數(shù)組不存在主要元素，比如1 2 1 2 3這個例子，1和2互相抵消，最后剩下3。

算法實現(xiàn)

public int majorityElement(int[] nums) {
    // 主要元素的候選人
    int major = nums[0];
    // major的計數(shù)器，即major的數(shù)量
    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這種情況
    // 所以還需要遍歷數(shù)組，計算major的出現(xiàn)次數(shù)，判斷是否大于數(shù)組一半
    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;
}