Reading · Swift by An Tran

This page did not load. You can still read it on the original site — the toolbar below keeps your place in the directory.

Leetcode: 169. Majority Element Primary idea: Boyer-Moore Majority Voting Algorithm Time Complexity: O(n), As two traversal of the array, is…

Leetcode: 169. Majority Element

Primary idea: Boyer-Moore Majority Voting Algorithm
Time Complexity: O(n), As two traversal of the array, is needed, so the time complexity is linear.
Space Complexity: O(1), As no extra space is required.

func majorityElement(_ nums: [Int]) -> Int {
    var count = 0, candidate = 0
    for num in nums {
        if count == 0 {
            candidate = num
        }
        count += (candidate == num) ? 1 : -1
    }
    return candidate
}
majorityElement([3,2,3]) // 3
majorityElement([2,2,1,1,1,2,2]) // 2
majorityElement([3, 3, 4, 2, 4, 4, 2, 4, 4]) // 4

iOS Interview - Leetcode 169. Majority Element

Further reading:

Comments