description

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
  • -109 <= nums[i] <= 109

 

Follow-up: Could you solve the problem in linear time and in O(1) space? ---

submission

// the gist of Boyer-Moore Majority Vote
// Algorithm: the majority element can 
// cancel out any other elements
impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        nums.into_iter()
            .fold((0, 0), |(val, cnt), num| {
                match (cnt == 0, val == num) {
                    // count == 0, use current element
                    (true, _) => (num, 1),
                    // count != 0, same element, increase count
                    (false, true) => (val, cnt + 1),
                    // count != 0, different element, cancel out
                    (false, false) => (val, cnt - 1),
                }
            })
            .0
    }
}