回答

[id:nuc:20061213:p13]
これで上手く行きそうだけど、未確認。

記憶領域をa,bと名づける。aには要素を記憶し、bはカウンタとして使う。

１パス目

aに最初の要素を記憶し、bに1をセットする。
２つ目以降の要素を見るたびに、

• aと同じなら、bを1つ増やし
• aと違うなら、bを1つ減らし
  • bが0になったら、aにその時点の要素を記憶し直す

走査が完了した時に、aに残っているのが候補。

２パス目

aに候補を記憶し、bに0をセットする。
全ての要素に対し、一つ一つ

• aと同じなら、bを1つ増やし
• aと違うなら、bを1つ減らす

b>0なら、過半数の要素はaで、そうでなければ、過半数の要素はない。