Leetcode - Majority Element

violet posted @ May 07, 2020 01:36:17 AM in 算法 with tags Algorithm array Golang , 199 阅读

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

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

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

Example 2:

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

func majorityElement(nums []int) int {
    candidate := nums[0]
    count := 0
    for _, n := range nums {
        if count == 0 {
            candidate = n
            count++
        } else {
            if candidate == n {
                count++
            } else {
                count--
            }
        }
    }
    return candidate
}