229. Majority Element II

https://leetcode.com/problems/majority-element-ii/

给定一个数组，其长度为 n, 找出其中出现次数超过 n/3 的数，可能有一个，也可能有两个
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]

分析：与 https://www.jianshu.com/p/adab40f7a25b 类似，可以从数组中同时减去3个不同的数字

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int ntms1=0, ntms2=0;
        int temp1=0, temp2=0;
        for(int i=0; i<nums.size(); ++i)
        {
            if(ntms1==0 && nums[i]!=temp2) //这里注意要加一个判断 nums[i]不等于temp2, 不加 [1,2,2,3,2,1,1,3]出错
            {
                temp1=nums[i];
                ntms1=1;
            }
            else if(temp1==nums[i])
            {
                ntms1++;
            }
            else if (ntms2==0)
            {
                temp2 = nums[i];
                ntms2 = 1;
            }
            else if (temp2==nums[i])
            {
                ntms2 ++;
            }
            else
            {
                ntms1--;
                ntms2--;
            }
        }

        ntms1=0,ntms2=0;
        for(int i=0; i<nums.size();++i)
        { 
            if(nums[i]==temp1)
                ntms1++;
            else if(nums[i]==temp2)
                ntms2++;
        }

        int k = (nums.size()/3);
        vector<int> result;
        if(ntms1>k)
            result.push_back(temp1);
        if(ntms2>k)
            result.push_back(temp2);
        return result;
    }
};

结果：

Runtime: 12 ms, faster than 88.67% of C++ online submissions for Majority Element II.
Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Majority Element II.