Loading…
Loading…
Finds the value occupying more than half the array with a single counter and no extra memory — different values simply cancel out.
The counter hit zero, so everything before this point has cancelled out exactly. Adopt a[0] = 3 as the new candidate with one vote.
1int majority(int[] a) {2 int candidate = 0, count = 0;3 for (int x : a) {4 if (count == 0) { candidate = x; count = 1; }5 else if (x == candidate) count++;6 else count--; // two different values cancel — that is the whole trick7 }8 int seen = 0;9 for (int x : a) if (x == candidate) seen++; // always verify: a candidate appears even with no majority10 return seen > a.length / 2 ? candidate : -1;11}