Boyer–Moore majority vote: co rozwiązuje i jaka jest główna idea?

Odpowiedź

Znajduje element występujący więcej niż n/2 razy (jeśli istnieje). Idea polega na „kasowaniu” par różnych elementów; pozostały kandydat to większość. Działa w O(n) czasu i O(1) pamięci.

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