Find the element that appears in more than half of a list using O(1) memory: keep one candidate and a counter, adding 1 when you see the candidate and subtracting 1 otherwise, switching candidates when the counter hits 0.
Implement:
majority(nums): the majority element, or None if there isn't one. The voting pass only finds a candidate, so verify it with a second pass.majority_third(nums): all elements appearing more than n/3 times, sorted, using the two-candidate generalisation (again verifying at the end)