SA
메인 내용으로 이동

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)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)O(1)

이 문서를 언급한 문서들