数组的多数元素指在数组中出现一半以上的元素，如果数组大小为7，那么多数元素至少出现4次，如果为8，至少出现5次。

求多数元素的方法中，时间和空间都较优秀的算法是投票算法，时间复杂度$O(n)$，空间复杂度$O(1)$。

投票算法思想为：将两个不同的数两两抵消，如果最后能剩下数，那么这个数就是多数元素，如果最后不剩元素，那么数组没有多数元素。

Boyer-Moore 投票算法的代码步骤如下：

维护一个候选主要元素 candidate 和候选主要元素的出现次数 count，初始时 candidate 为任意值，count=0；

遍历数组 nums 中的所有元素，遍历到元素 x 时，进行如下操作：

如果 count=0，则将 x 的值赋给 candidate，否则不更新 candidate 的值；

如果 x=candidate，则将 count 加 1，否则将 count 减 1。

遍历结束之后，如果数组 nums 中存在主要元素，则 candidate 即为主要元素，否则 candidate 可能为数组中的任意一个元素。

int majorityElement(int* nums, int numsSize) {
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < numsSize; i++) {
        if (count == 0) {
            candidate = nums[i];
        }
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    count = 0;
    int length = numsSize;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate) {
            count++;
        }
    }
    return count * 2 > length ? candidate : -1;
}