Question: https://leetcode.com/problems/majority-element/
Question Name: Majority Element
We can do it with a dictionary (O(N) time, O(N) space). For a better solution with O(N) time and O(1) space, we can remove pairs of different elements as many as possible, and the remaining unique element is the majority.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution: # @param num, a list of integers # @return an integer def majorityElement(self, num): major = num[0] majorTimes = 1 for number in num[1:]: if number == major: # Same element appear again. majorTimes += 1 elif majorTimes == 0: # Try another element as candidate. majorTimes = 1 major = number else: # Different element appear. majorTimes -= 1 return major |