CMPSC 130A Lecture Notes - Lecture 1: Xm Satellite Radio
Document Summary
Identify the one that occurs at least n/2 (the majority) times. Your algorithm has access to only limited memory. Solution: two things to store in memory: (a) id (b) count. Set id to the specific element, and increment/decrement count if the current element is/is not equal to id. If id is the majority, count > 0. Proof of correctness: suppose item z is the majority item. Z must become majority candidate m at some point. While m = z, only non-z items cause count to decrement. Each non-z item can only cancel one occurrence of z. But in total, we have fewer than n/2 non-z items; they cannot cancel all occurrences of z. So in the end, z must be stored as m, with a non-zero count c. M may contain a random item, with non-zero c. A second pass through the sequence is necessary to confirm that m is in fact the majority.
