Boyer-Moore（摩尔投票算法）求多数元素

Problem:

Imagine that you have a non-sorted list of values. You want to know if there is a value that is present in the list for more than half of the elements in that list. If so what is that value? If not, you need to know that there is no majority element. You want to accomplish this as efficiently as possible.

Solution1:

如果多数元素一定存在，进行排序后，则中间元素为多数元素。如果不一定存在，进行排序后，取中间元素为候选数，进行一次迭代，确定候选数是否为多数元素。

int majority(std::vector<int> nums) {
        std::sort(nums.begin(), nums.end());
        int candidate = nums[nums.size() / 2];

        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == candidate) {
                cnt++;
            }
        }
        return (cnt > nums.size() / 2) ? candidate : -1;
    }

Explanation:

时间负责度: O(N) = O(nlogn + n) = O(nlogn)
 没有学习过摩尔投票算法的同学，排序取中是较为常见的算法。但排序期间存在太多冗余运算，摩尔投票算法有效地优化了计算过程。

Step 1
 T candidate = anyValue，初始值可为任意值
Step 2
 int count = 0,初始值为0
Step 3
 迭代数组，如果count为0, 赋值当前元素予candidate，且count自加1； 如果元素与candidate相等，count自加1，否则自减1。
Step 4
 返回candidate，进行迭代，若candidate在数组出现次数大于数组size一半，则为多数元素，否则不存在多数元素。

代码如下

int majority(std::vector<int> nums) {
        std::sort(nums.begin(), nums.end());
        int candidate = nums[nums.size() / 2];

        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == candidate) {
                cnt++;
            }
        }
        return (cnt > nums.size() / 2) ? candidate : -1;
    }

int candidate(std::vector<int> nums) {
        int cnt = 0;
        int candidate = 0; //could be any value
        for (int i = 0; i < nums.size(); i++) {
            if (cnt == 0) {
                candidate = nums[i];
                cnt++;
            }
            else if (candidate == nums[i]) {
                cnt++;
            }
            else {
                cnt--;
            }
        }
        return candidate;
    }

时间复杂度 O(N) = O(2n) = O(n)