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)

References

  1. 169. Majority Element