메인 내용으로 이동

# 0169 Majority Element

Solved at: 2023-01-28

Majority Element

## Question​

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.

## Solution​

class Solution {    func majorityElement(_ nums: [Int]) -> Int {        var map = [Int: Int]()        for num in nums {            if map.keys.contains(num) {                map[num]! += 1            }            else {                map[num] = 1            }        }        var maxVal = 0        var maxKey = 0        for (idx, (key, val)) in map.enumerated() {            if val > maxVal {                maxVal = val                maxKey = key            }        }        return maxKey    }}

## Results​

• Runtime 102 ms, Beats 76.95%
• Memory 15.8 MB, Beats 65.42%

## Complexity Analysis​

$O(n)$ for both

## Improved​

### Boyer-Moore Voting Algorithm​

using you cannot discard the majority item

class Solution {    func majorityElement(_ nums: [Int]) -> Int {        var count : Int = 0        var candidate: Int? = nil        for num in nums {            if count == 0 {                candidate = num            }            if candidate == num {                count += 1            } else {                count -= 1            }        }        return candidate!    }}

This gives space complexity $O(1)$