題目： LeetCode - 169. Majority Element

題目說明

給一個陣列，求此陣列中出現最多次的數字。

解題思路

  • 想法： 想像成是消去法，將數字兩兩消去，最後剩下的一定是出現最多次的那個數字。

  • 作法： 定義一個 num 紀錄數字，count 紀錄該數字出現的次數。使用一個迴圈，當碰到數字和 num 不同時就把 count - 1，若 count 剩下 0 時，把 num 換成該數，count 設為 1。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int num, count = 0;
        for(auto i : nums)
            if(i == num)
                ++count;
            else if(--count <= 0)
                num = i, count = 1;
        return num;
    }
};