169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

---

要求出一个数组中的多数元素，这里的多数元素是指出现次数多于数组长度的一半。 很有意思的一个题目，前几天听旁边一个组的同学面试回来就说被问到了这个题。 常规思路是把数组排序，然后取⌊ n/2 ⌋这个元素，这种思路的算法复杂度为$O(nlgn)$的代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

本代码提交AC，用时52MS。
还有另一种巧妙的思路，假设一个数组是[1,1,2,2,1,1,3,1]，多数元素是1，如果从数组中同时删除元素1和2，剩余的数组[1,2,1,1,3,1]中，多数元素还是1。也就是说从数组中删除两个不同的元素，剩余数组中的多数元素和原数组中的多数元素是一样的。这种算法好像叫做摩尔投票法。
根据这种思路，我们定义两个变量ans和cnt，初始时cnt=0。当cnt==0时，此时是原始数组或者删除了两个不同的元素。以后每次，遇到和ans相同的元素，cnt++，否则cnt–。cnt–就相当于删掉两个不同的元素。
这种思路只需要遍历一遍原数组，时间复杂度是$O(n)$，完整代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        int ans, cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (cnt == 0) {
                ans = nums[i];
                cnt++;
            }
            else {
                if (nums[i] == ans)
                    cnt++;
                else
                    cnt–;
            }
        }
        return ans;
    }
};

本代码提交AC，用时22MS。果然比之前的快很多。