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]

Difficulty: interview

Starter code:

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        

Solutions:
class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         if nums == []:
             return []
         
         dct = {}
         for el in nums:
             if el in dct:
                 dct[el] += 1
             else:
                 dct[el] = 1
             
         fin = []
         for key in dct:
             if dct[key] > (len(nums) // 3):
                 fin.append(key)
         
         return fin
         


class Solution:
     def majorityElement(self, nums):
         d = {}
         for i in nums:
             if i in d:
                 d[i] += 1
             else:
                 d[i] = 1
         
         l = []
         for i in list(d.keys()):
             if d[i] > len(nums) // 3:
                 l.append(i)
                 
         return l
                 
         
         


class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         if not nums:
             return([])
         
         l = len(nums)
         candidate1 = candidate2 = 0
         count1 = count2 = 0
         
         for i in nums:
             if candidate1 == i:
                 count1 += 1
             elif candidate2 == i:
                 count2 += 1
             elif count1 == 0:
                 candidate1 = i
                 count1 = 1 
             elif count2 == 0:
                 candidate2 = i
                 count2 = 1
             else:
                 count1 -= 1
                 count2 -= 1
             
         c1 = nums.count(candidate1)
         c2 = nums.count(candidate2)
     
         res = []
         if c1 > l/3:
             res.append(candidate1)
         if c2 > l/3 and candidate1 != candidate2:
             res.append(candidate2)
         
         return(res)


class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         if len(nums)<=2:
             return list(set(nums))
         can,can2 = 0,0
         num,num2 = 0,1
         for i in range(len(nums)):
             if nums[i]==can:
                 num+=1
             elif nums[i] == can2:
                 num2 +=2
             elif num ==0:
                 num=1
                 can = nums[i]
             elif num2==0:
                 num2=1
                 can2 = nums[i]
             else:
                 num,num2=num-1,num2-1
         res = []
         if nums.count(can)>int(len(nums)/3):
             res.append(can)
         if nums.count(can2)>int(len(nums)/3) and can2!=can:
             res.append(can2)
         return res

class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         length=len(nums)
         ans=[]
         for i in set(nums):
             if nums.count(i)>length/3:
                 ans.append(i)
         return ans

class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         n1 = n2 = None
         c1 = c2 = 0
         
         for i in nums:
             if n1 == i:
                 c1 += 1
             elif n2 == i:
                 c2 += 1
             elif c1 == 0:
                 n1, c1 = i, 1
             elif c2 == 0:
                 n2, c2 = i, 1
             else:
                 c1, c2 = c1 - 1, c2 -1
         return [n for n in [n1, n2] if n is not None and nums.count(n) > len(nums)//3]


class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         ans = []
         
         if not nums:
             return []
         
         a1 = a2 = None
         c1 = c2 = 0
         
         for num in nums:
             if a1 == num:
                 c1 += 1
             elif a2 == num:
                 c2 += 1
             elif c1 == 0:
                 a1, c1 = num, 1
             elif c2 == 0:
                 a2, c2 = num, 1
             else:
                 c1 -= 1
                 c2 -= 1
         
         c1 = c2 = 0
         
         for num in nums:
             if num == a1:
                 c1 += 1
             elif num == a2:
                 c2 += 1
         
         for a, c in ((a1, c1), (a2, c2)):
             if c > len(nums) // 3:
                 ans.append(a)
         
         return ans

class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         dic = {}
         res = []
         n = len(nums)
         for i in range(n):
             dic[nums[i]] = dic.get(nums[i], 0) + 1
         print(dic)
         for num, cnt in dic.items():
             if cnt > n/3:
                 res.append(num)
         return res

class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         ret = []
         least = len(nums) / 3
         h = {}
         for n in nums:
             if n in list(h.keys()):
                 h[n] += 1
             else:
                 h[n] = 1
                 
             if h[n] > least and n not in ret:
                 ret.append(n)
                 
         return ret
             


class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         N = len(nums)
         N3 = N/3
         nums.sort()
         result = []
         if N < 1:
             return nums
         
         _cnt = 0
         _num = nums[0]
         
         for n in nums:
             if n != _num:
                 if _cnt > N3:
                     result.append(_num)
                 _cnt = 1
                 _num = n
             else:
                 _cnt += 1
         else:
             if _cnt > N3:
                 result.append(_num)
         
         
         return result

class Solution:
     def majorityElement(self, nums):
         ctr = collections.Counter()
         for n in nums:
             ctr[n] += 1
             if len(ctr) == 3:
                 ctr -= collections.Counter(set(ctr))
         return [n for n in ctr if nums.count(n) > len(nums)//3]
         """
         :type nums: List[int]
         :rtype: List[int]
         """


class Solution:
     def majorityElement(self, nums):
         """
         :type nums: List[int]
         :rtype: List[int]
         """
         d = dict()
         results = []
         for num in nums:
             d[num] = d.get(num,0) + 1
             if d[num] > len(nums) // 3:
                 if num not in results:
                     results.append(num)
         return results