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

Source: leetcode | Difficulty: EASY
Tags: Sorting

Data structures

Mathematics

Divide and conquer

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

Solutions:
class Solution:

	def majorityElement(self, nums):
		n = len(nums)
		if n == 1:
			return nums[0]
		if n % 2:
			find = set(nums[0:n // 2 + 1]) & set(nums[n // 2:])
		else:
			find = set(nums[0:n // 2]) & set(nums[n // 2:])
		for i in find:
			if nums.count(i) > n // 2:
				return i


class Solution:

	def majorityElement(self, nums):
		order = dict()
		if len(nums) > 1:
			for i in range(len(nums)):
				if nums[i] in list(order.keys()):
					order[nums[i]] += 1
					if order[nums[i]] > len(nums) // 2:
						return nums[i]
				else:
					order[nums[i]] = 1
		else:
			return nums[0]


class Solution:

	def majorityElement(self, nums):
		l = len(nums)
		for n in set(nums):
			if nums.count(n) > l / 2:
				return n


class Solution:

	def majorityElement(self, nums):
		count = 0
		candidate = None
		for num in nums:
			if count == 0:
				candidate = num
			count += 1 if num == candidate else -1
		return candidate


class Solution:

	def majorityElement(self, nums):
		map = {}
		for n in nums:
			if n not in map:
				map[n] = 0
			map[n] += 1
		(max, occ) = (-1, -1)
		for (num, count) in map.items():
			if count > occ:
				(max, occ) = (num, count)
		return max


class Solution:

	def majorityElement(self, nums):
		a = sorted(nums)
		return a[int(len(a) / 2)]


class Solution:

	def majorityElement(self, nums):
		if not nums:
			return ''
		current = nums[0]
		counter = 1
		for i in range(1, len(nums)):
			if counter == 0:
				current = nums[i]
				counter = 1
			elif nums[i] == current:
				counter += 1
			else:
				counter -= 1
		return current


class Solution:

	def majorityElement(self, nums):
		table = {}
		for num in nums:
			if num not in table:
				table[num] = 1
			else:
				table[num] += 1
		sorting_tutple = [(value, key) for (key, value) in list(table.items())]
		sorting_tutple.sort(reverse=True)
		return sorting_tutple[0][1]


class Solution:

	def majorityElement(self, nums):
		d = {}
		maxV = float('-inf')
		maxX = -1
		n = len(nums) // 2
		for x in nums:
			if x not in d:
				d[x] = 1
			else:
				d[x] += 1
			if d[x] > maxV:
				maxV = d[x]
				maxX = x
			if maxV > n:
				break
		return maxX


class Solution:

	def majorityElement(self, nums):
		hist = {}
		for num in nums:
			if num not in hist:
				hist[num] = 0
			hist[num] += 1
			if hist[num] > len(nums) // 2:
				return num


class Solution:

	def majorityElement(self, nums):
		s = {}
		for i in range(len(nums)):
			s[nums[i]] = s.get(nums[i], 0) + 1
		for num in nums:
			if s[num] > len(nums) // 2:
				return num


class Solution:

	def majorityElement(self, nums):
		ele = {}
		for i in nums:
			if i in ele:
				ele[i] += 1
			else:
				ele[i] = 1
			if ele[i] > len(nums) / 2:
				return int(i)


class Solution:

	def majorityElement(self, nums):
		count = {}
		for i in nums:
			if i in count.keys():
				count[i] += 1
			else:
				count[i] = 1
		ans = count[nums[0]]
		res = nums[0]
		for x in count.keys():
			if count[x] > ans:
				ans = count[x]
				res = x
		return res