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.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
Solutions
1. Sort
要求找到占一半以上的数,那么排序找中间数即可。
# Time: O(nlogn)
# Space: O(n)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]
# 44/44 cases passed (172 ms)
# Your runtime beats 85.91 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (14 MB)
2. Bit Manipulation
占据一半以上的数有一个特点就是,从 bit 位上看:
- 每一位上的 1 或 0 都是占大多数的(每个数位上一般以上是啥,最终结果在该数位上肯定是啥)
- 所以只需要在外层遍历 32 位的每一位,然后将 1 左移遍历指针 i,让 i 位为 1,其他为 0,统计 1 的个数
- 如果超过半数,则最后结果在该位上为 1,用结果值与该位取或
- 如果没有超过一般,则最后结果该位上为 0,不作额外才做,默认就为零。
# Time: O(n)
# Space: O(n)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
n = len(nums)
majority = 0
for i in range(32):
mask = 1 << i
count = 0
for num in nums:
if num & mask:
count += 1
if count > n // 2:
majority |= mask
return majority if majority >> 31 == 0 else majority - (1 << 32)
# 44/44 cases passed (172 ms)
# Your runtime beats 85.91 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (14 MB)