169. Majority Element
https://leetcode.com/problems/majority-element/#/description
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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.Subscribe to see which companies asked this question.
Hide Tags
Array Divide and Conquer Bit Manipulation
Hide Similar Problems
思路
- 其實(shí)很簡(jiǎn)單寄猩，這種類似的題目都是建立字典即
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1:
return nums[0]
d = {}
for num in nums:
if num in d.keys():
d[num] += 1
if d[num] >= len(nums) // 2:
return num
else:
d[num] = 0
229. Majority Element II
https://leetcode.com/problems/majority-element-ii/#/description
Given an integer array of size n, find all elements that appear more than ? n/3 ? times. The algorithm should run in linear time and in O(1) space.
Subscribe](https://leetcode.com/subscribe/) to see which companies asked this question.
Hide Tags
Hide Similar Problems
