text: /*
   * @lc app=leetcode id=169 lang=cpp
   *
   * [169] Majority Element
   */
  
  // @lc code=start
  class Solution {
  public:
      int majorityElement(vector<int>& nums) {
          // // bit-manipulation
          // // The bits in the majority are just the majority bits of all numbers
          // // Time: O(n); Space: O(1)
          // vector<int> bit(32, 0);
          // for (int num: nums) {
          //     for (int i = 0; i < 32; i++) {
          //         bit[i] += (num>>i) & 1;
          //     }
          // }
          // int res = 0;
          // for (int i = 0; i < 32; i++) {
          //     if (bit[i] > nums.size()/2) {
          //         res |= (1<<i);
          //     }
          // }
          // return res;
  
          // Boyer-Moore Voting Algorithm
          // https://zhuanlan.zhihu.com/p/104609555
          int majority = nums[0], count = 1;
          for (int i = 1; i < nums.size(); i++) {
              if (nums[i] == majority) count++;
              else {
                  if (count > 0) count--;
                  else {
                      count = 1;
                      majority = nums[i];
                  }
              }
          }
          return majority;
      }
  };
  // @lc code=end
  
  