# 229. Majority Element II (medium)

###### tags: `online_judge`, `python3`

自我挑戰型的 medium 題。找出給定的數列中，佔數列超過 3 分之 1 的元素。

題目要求使用線性時間複雜度及 O(1) 的空間複雜度。然而並沒有給定數列中元素的大小範圍，想要決定使用不需 hash 的陣列還是用 hash table 就成了難題。我這邊乾脆兩種方法都放。

基本上使用陣列不需要 hash，計算量較少但空間需求大。而 hash table 使用前需要對 key 先進行 hash，計算量大但空間需求小。假如有給定元素大小範圍的話倒是可以事前決定要用那一種....

最後還是老話一句，題目沒給數值範圍，那就老老實實的考慮邊緣狀況吧，肯定會有坑的。

---

### 題目

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]

---

### 解答

class Solution:
    def majorityElement(self, nums):
		
        if not nums:
            return []
        
        ans = []
        max_num = max(nums)
        min_num = min(nums)
        pass_bound = len(nums)/3
        if max_num - min_num < 50000:
            map_count=[0]*(max_num - min_num + 1)
            for i in range(len(nums)):
                map_count[nums[i]- min_num] += 1
            for i in range(max_num - min_num + 1):
                if map_count[i] > pass_bound:
                    ans.append(i + min_num)		
            return ans
        else:
            hash_count = {}
            for i in range(len(nums)):
                if not hash_count.__contains__(nums[i]):
                    hash_count[nums[i]] = 1;
                else:
                    hash_count[nums[i]] += 1
            for i, j in hash_count.items():
                if j > pass_bound:
                    ans.append(i)
            return ans
    
a = Solution()
print (a.majorityElement([3,2,3]))
print (a.majorityElement([1,1,1,3,3,2,2,2]))
print (a.majorityElement([]))
print (a.majorityElement([0,-1,2,-1]))

---
### 成績


---