Leaderを選ぶアルゴリズム

　CodilityのlessonにあるLeaderを選ぶアルゴリズムが面白い。

非負整数を要素に持つ長さnの配列a[]がある。
配列の中にn/2 回より多く出現する要素がある場合、その要素を配列のleaderと呼ぶ。

例えば、
[1,2,3,1,1,1]
という配列の場合、1がleader。

[1,1,1,2,3,4]
の場合は、leader不在となる。

配列a[]が与えられた時に、a[]のleaderを求めよ。

mapを使って要素毎の出現回数を数えるだけでしょ。
と思ったら、時間計算量の制限はO(n)らしい。

それなら、unodered_mapで数えればいいでしょ。
と思ったら、空間計算量（※）はO(1)らしい。
（※入力aを格納するのに必要なメモリは除く）

いや、分かりません。
ということでマテリアルを読むと、スタックを使ったクレバーな解が紹介されてました。
C++で書いてみました。

#include <iostream>
#include <vector>

using namespace std;

int leader(const vector<int> &a) {
  int n = a.size();
  int sz = 0;  // stack size
  int val;     // value in stack
  
  for (auto &x : a) {
    if (sz == 0) {
      ++sz;
      val = x;
    } else {
      if (val != x)
        --sz;
      else
        ++sz;
    }
  }

  if (sz && count(a.begin(), a.end(), val) > n / 2)
    return val;

  return -1;  // no leader
}

int main() {
  cout << leader({1,2,3,1,1,1}) << endl;
  cout << leader({1,1,1,2,3,4}) << endl;
  cout << leader({2,3,4,1,1,1}) << endl;

  return 0;
}