In an initial scan, keep track of the best candidate majority value, x, and a counter that keeps track of the number of times you have seen a copy of x versus some other integer.