229. Majority Element II2

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

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

Example 2:

Input: [1,1,1,3,3,2,2,2] Output: [1,2]29. Majority Element II

---

本题要求一个数组中出现次数大于 ⌊ n/3 ⌋的所有数字，上一题LeetCode Majority Element是求数组中出现次数大于 ⌊ n/2 ⌋的数字，而且保证数组中有且仅有一个这样的众数。 在本题中，并不一定存在符合题意的众数存在，如果存在，最多有2个这样的众数，可以用反证法，如果有3个这样的众数，那么每个元素的出现次数最多是n/3，不可能超过。 思路还可以用上一题的摩尔投票法，即我们假设最多存在两个这样的众数，且随便设置这两个不同的众数为0和1，然后用摩尔投票法过一遍数组，看看最终记录的众数是哪两个。 最后再过一遍数组，统计一下这两个数的次数是否超过n/3。 完整代码如下：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums)
    {
        int num1 = 0, num2 = 1, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == num1) { // (1)
                cnt1++;
            }
            else if (nums[i] == num2) { // (2)
                cnt2++;
            }
            else if (cnt1 == 0) { // (3)
                num1 = nums[i];
                cnt1++;
            }
            else if (cnt2 == 0) { // (4)
                num2 = nums[i];
                cnt2++;
            }
            else {
                cnt1–;
                cnt2–;
            }
        }
        vector<int> ans;
        cnt1 = 0;
        cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == num1)
                cnt1++;
            else if (nums[i] == num2)
                cnt2++;
        }
        if (cnt1 > nums.size() / 3)
            ans.push_back(num1);
        if (cnt2 > nums.size() / 3)
            ans.push_back(num2);
        return ans;
    }
};

注意代码中的(1)(2)判断必须在(3)(4)判断前面，因为如果遇到[8,8,7,7,7]这样的样例，如果(3)(4)在前面的话，num1和num2就都会被赋值为8，导致丢掉了8这个结果。还有我们一开始必须给num1和num2随便设置不同的两个数。
本代码提交AC，用时16MS。

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。果然比之前的快很多。