169_多数元素

类型：数组

• 169. 多数元素 💚 ⭐

  https://leetcode-cn.com/problems/majority-element/

  ❓ 从长度为 n 的数组 nums 中找出多数（出现次数大于 n/2）元素。假定多数元素必然存在。

  💡 投票法

  class Solution:
      def majorityElement(self, nums: List[int]) -> int:
          count = 0
          candidate = None
  
          for num in nums:
              if count == 0:
                  candidate = num
              count += (1 if num == candidate else -1)
  
          return candidate

  时间复杂度：O(n)，空间复杂度：O(1)

  💡 哈希表

  class Solution:
      def majorityElement(self, nums: List[int]) -> int:
          counts = collections.Counter(nums)
          return max(counts.keys(), key=counts.get)

  时间复杂度：O(n)，空间复杂度：O(1)

  💡 排序

  如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n//2 的元素（下标从 0 开始）一定是众数。

  class Solution:
      def majorityElement(self, nums: List[int]) -> int:
          nums.sort()
          return nums[len(nums) // 2]

  时间复杂度：O(NlogN)，空间复杂度：O(n)

  💡 随机试探

  既然众数的出现概率高，我们随机挑选一个下标对应的元素并对其进行验证，有很大的概率能找到众数。

  class Solution:
      def majorityElement(self, nums: List[int]) -> int:
          majority_count = len(nums) // 2
          while True:
              candidate = random.choice(nums)
              if sum(1 for elem in nums if elem == candidate) > majority_count:
                  return candidate

  时间复杂度：最坏的话是O(∞)，平均来说，我们试探到众数的概率是常数，验证的复杂度是 O(n)，最终平均下来是 O(n)

  空间复杂度：O(1)