Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

 

思路：

　　【LeetCode 169】Majority Element 的拓展，这回要求的是出现次数超过三分之一次的数字咯，动动我们的大脑思考下，这样的数最多会存在几个呢，当然是2个嘛。因此，接着上一题的方法做，只不过这回要投两个票啦，而且最后还得检查这两个投票结果是不是真的满足都超过三分之一，因为这一题题目什么都没有保证，所以答案可能有0个、1个、2个。

C++：

1 class Solution { 2 public: 3     vector
     
       majorityElement(vector
      
       & nums) { 4         vector
       
         ret; 5          6         int len = nums.size(); 7         if(len == 0) 8             return ret; 9         10         int m = 0, n = 0, cm = 0, cn = 0;11         for(int i = 0; i < len; i++)12         {13             int val = nums[i];14             if(m == val)15                 cm++;16             else if(n == val)17                 cn++;18             else if(cm == 0)19             {20                 m = val;21                 cm = 1;22             }23             else if(cn == 0)24             {25                 n = val;26                 cn = 1;27             }28             else29             {30                 cm--;31                 cn--;32             }33         }34         35         cm = cn = 0;36         37         for(int i = 0; i < len; i++)38         {39             if(nums[i] == m)40                 cm++;41             else if(nums[i] == n)42                 cn++;43         }44         45         if(cm * 3 > len)46             ret.push_back(m);47         if(cn * 3 > len)48             ret.push_back(n);49         50         return ret;51     }52 };
       
      
     

 

Python：

1 class Solution: 2     # @param {integer[]} nums 3     # @return {integer[]} 4     def majorityElement(self, nums): 5         m, n, cm, cn = 0, 0, 0, 0 6         ret = [] 7          8         for val in nums: 9             if m == val:10                 cm = cm + 111             elif n == val:12                 cn = cn + 113             elif cm == 0:14                 m = val15                 cm = 116             elif cn == 0:17                 n = val18                 cn = 119             else:20                 cm = cm - 121                 cn = cn - 122         23         cm, cn = 0, 024         25         for val in nums:26             if m == val:27                 cm = cm + 128             elif n == val:29                 cn = cn + 130         31         if cm * 3 > len(nums):32             ret.append(m)33         if cn * 3 > len(nums):34             ret.append(n)35         36         return ret