题解 | #微信红包# Boyer-Moore 算法

参考力扣169.多数元素

https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

class Gift {
  public:
    int getValue(vector<int> gifts, int n) {
        int candidate = gifts[0];
        int count = 1;
        for (int i = 1; i < n; i++) {
            if (gifts[i] == candidate) {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                candidate = gifts[i];
                count = 1;;
            }
        }
        if (count > 1) {
            return candidate;
        }
        return 0;
    }
};

时间复杂度：O(n)，只遍历了一次数组

空间复杂度：O(1)，没有使用额外的空间