题解 | #数组中出现次数超过一半的数字#

方法：个数统计

具体做法：

1. 初始化：候选人cond = -1， 候选人的投票次数cnt = 0
2. 遍历数组，如果cnt=0， 表示没有候选人，则选取当前数为候选人，++cnt
3. 否则，如果cnt > 0, 表示有候选人，如果当前数=cond，则++cnt，否则--cnt
4. 直到数组遍历完毕，最后检查cond是否为众数

时间复杂度：o(n)。遍历数组需要时间o(n)。

空间复杂度：o(1)。不需要额外空间。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        int cnt = 0;
        int target = 0;

        for(int i = 0; i < numbers.size(); i++) {
            if(cnt == 0 || numbers[i] == target) {
                cnt++;
                target = numbers[i];
            } else {
                cnt--;
            }
        }
        return target;
    }
};

方法：哈希表

此方法不满足题目中复杂度的要求，提供用于拓展视野。

利用哈希表存储数组中的值，value设置为数字出现的次数。当次数大于数组长度的一半时，就得到了目标值。

时间复杂度：o(n)。需要遍历数组

空间复杂度：o(n)。构建哈希表需要额外空间

class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        unordered_map<int, int> hash;
        int i = 0;
        for (i = 0; i < numbers.size(); i++) {
            if (hash.find(numbers[i]) == hash.end())
                hash[numbers[i]] = 1;
            else
                hash[numbers[i]]++;

            if (hash[numbers[i]] > numbers.size() / 2) {
                break;
            }
        }
        return numbers[i];
    }
};

方法：排序法

具体做法：将数组进行排序，数组的中间值即为目标值。

时间复杂度：o(nlogn)。

空间复杂度：o(1)。

class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size() / 2];
    }
};