Majority Number 系列

相关题目:

感觉这三题比较 tricky。

Majority Number 解法的具体解释见 Boyer–Moore majority vote algorithm - Wikipedia, the free encyclopedia。以下是实现。

class Solution {  
public:  
  int majorityNumber(vector<int> nums) {
    int majority = 0, count = 0;
    for (int num : nums) {
      if (count == 0) {
        majority = num;
        count = 1;
      } else if (majority == num) {
        ++count;
      } else {
        --count;
      }
    }
    return majority;
  }
};

Majority Number II/IIIMajority Number 的推广,分别考察占比阈值为 $1/3$ 与 $1/k$ 的情况。

以下是关键结论:

  1. 考虑阈值为 $1/k$ 的情况, 最多只会有 $k - 1$ 个的 majority numbers
  2. 在最后需要扫一次 $nums$ 验证得到的是的确是 majority number。 (LintCode 里已经保证了有且仅有一个 majority number,判断会简单很多)

以下是 Majority Number II 的实现。

class Solution {  
 public:
  int majorityNumber(vector<int> nums) {
    int val1 = 0, cnt1 = 0;
    int val2 = 0, cnt2 = 0;

    for (int num : nums) {
      if (cnt1 > 0 && val1 == num) {
        ++cnt1;
      } else if (cnt2 > 0 && val2 == num) {
        ++cnt2;
      } else if (cnt1 == 0) {
        val1 = num;
        cnt1 = 1;
      } else if (cnt2 == 0) {
        val2 = num;
        cnt2 = 1;
      } else {
        --cnt1;
        --cnt2;
      }
    }

    cnt1 = cnt2 = 0;
    for (int num : nums) {
      if (num == val1) {
        ++cnt1;
      } else if (num == val2) {
        ++cnt2;
      }
    }
    return (cnt1 > cnt2) ? val1 : val2;
  }
};

以下是 Majority Number III 的实现.

class Solution {  
 public:
  int majorityNumber(vector<int> nums, int k) {
    vector<int> counter(k - 1, 0);
    vector<int> values(k - 1, 0);

    for (int num : nums) {
      bool num_exists = false;
      for (int i = 0; i < k - 1; ++i) {
        if (counter[i] > 0 && values[i] == num) {
          ++counter[i];
          num_exists = true;
          break;
        }
      }
      if (num_exists) {
        continue;
      }

      bool num_added = false;
      for (int i = 0; i < k - 1; ++i) {
        if (counter[i] == 0) {
          values[i] = num;
          counter[i] = 1;
          num_added = true;
          break;
        }
      }
      if (num_added) {
        continue;
      }

      for (int i = 0; i < k - 1; ++i) {
        --counter[i];
      }
    }

    unordered_map<int, int> val_to_idx;
    for (int i = 0; i < k - 1; ++i) {
      counter[i] = 0;
      val_to_idx[values[i]] = i;
    }
    for (int num : nums) {
      if (val_to_idx.count(num) == 0) {
        continue;
      }
      ++counter[val_to_idx[num]];
    }

    for (int i = 0; i < k - 1; ++i) {
      if (counter[i] * k > nums.size()) {
        return values[i];
      }
    }
  }
};