LeetCode: 169. Majority Element

题目

原题地址： https://leetcode.com/problems/majority-element/

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -231 <= nums[i] <= 231 - 1

题目大意是，找出数组中出现次数大于 n/2 的元素。

解法

最简单的方法就是遍历数组，在遍历数组的过程中记录各个元素出现的次数（可以使用 hashmap 记录）， 当找到出现次数大于 n/ 的元素时直接返回该元素

这个思路的 Python 代码类似下面这样：

class Solution:
    def majorityElement(self, nums):
        counter = {}
        n = len(nums)

        for element in nums:
            if element not in counter:
                counter[element] = 0

            counter[element] += 1
            if counter[element] > n/2:
                return element

Comments