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]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Mathematics

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

Solutions:
class Solution:

	def majorityElement(self, nums):
		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):
		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):
		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):
		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):
		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):
		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):
		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):
		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):
		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]


class Solution:

	def majorityElement(self, nums):
		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