leetcode題目：

image.png

首先我用用了個Map，一旦出現(xiàn)計數(shù)超過數(shù)組長度一半，直接return。通過。
但是覺得這道題的關(guān)鍵之處在于一個數(shù)組中計數(shù)超過數(shù)組長度一半的數(shù)字只可能存在一個。
網(wǎng)上查了一通，知道了摩爾投票法的算法，學習了一下：
摩爾投票法的基本思想很簡單，在每一輪投票過程中，從數(shù)組中找出一對不同的元素，將其從數(shù)組中刪除。這樣不斷的刪除直到無法再進行投票，如果數(shù)組為空，則沒有任何元素出現(xiàn)的次數(shù)超過該數(shù)組長度的一半。如果只存在一種元素，那么這個元素則可能為目標元素。
下面是c++代碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = -1;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (count == 0) {
                major = nums[i];
                count++;
            } else {
                if (nums[i] == major) {
                    count++;
                }else {
                    count--;
                }
            }
        }
        return major;
    }
};

執(zhí)行結(jié)果：

image.png