LeetCode刷題記錄--面試題 17.10. 主要元素

面試題 17.10. 主要元素

如果數組中多一半的數都是同一個，則稱之為主要元素。給定一個整數數組，找到它的主要元素。若沒有，傳回-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) 内完成嗎？

根據題目要求，使用摩爾投票法：

摩爾投票算法是基于這個事實：每次從序列裡選擇兩個不相同的數字删除掉（或稱為“抵消”），最後剩下一個數字或幾個相同的數字，就是出現次數大于總數一半的那個。

int majorityElement(int* nums, int numsSize){
    int res = nums[0];
    int count = 1;
    int i;
    for (i = 1; i < numsSize; i++) {
        int temp = nums[i];
        if (count == 0) {
            res = temp;
            count = 1;
        } else {
            if (res == temp) {
                count++;
            } else {
                count--;
            }
        }
    }
    if (count == 0) {
        return -1;
    }
    return res;
}