Majority Element in an Array

easy array voting

Problem

An array contains a value that appears strictly more than ⌊n / 2⌋ times. Return that value using O(1) extra space. The Boyer–Moore voting idea: imagine each occurrence of the majority cancelling one occurrence of every other value — at least one majority instance must survive.

Inputnums = [4, 2, 4, 5, 4, 4, 1]

Output4

4 appears 4 times, more than 7 / 2 = 3.

nums (comma-separated)

def majority(nums):
    cand, count = None, 0
    for x in nums:
        if count == 0:
            cand = x
        count += 1 if x == cand else -1
    return cand

function majority(nums) {
  let cand = null, count = 0;
  for (const x of nums) {
    if (count === 0) cand = x;
    count += (x === cand) ? 1 : -1;
  }
  return cand;
}

class Solution {
    public int majority(int[] nums) {
        Integer cand = null;
        int count = 0;
        for (int x : nums) {
            if (count == 0) cand = x;
            count += (x == cand) ? 1 : -1;
        }
        return cand;
    }
}

int majority(vector<int>& nums) {
    int cand = 0, count = 0;
    for (int x : nums) {
        if (count == 0) cand = x;
        count += (x == cand) ? 1 : -1;
    }
    return cand;
}

Time: O(n) Space: O(1)