题目分析

来一道简单题目给小伙伴们放松放松，小伙伴们能优化到什么程度呢？能否在$O(n)$的时间复杂度内完成？能否在$O(1)$的空间复杂度完成？如果可以能否同时满足两个要求呢？

排序求解

因为数组中主要元素超过一半，因此我们将数组进行排序后，连续长度一定超过数组长度的一半。我们从0号元素遍历到nums.size() - num.size() / 2，如果存在nums[i] == nums[i + num.size() / 2]说明该元素是主要元素，否则返回-1。

主要时间在数组的排序，算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i + nums.size() / 2 < nums.size(); i++) if (nums[i] == nums[i + nums.size() / 2]) return nums[i];
        return -1;
    }
};

哈希表

最简单的方法是哈希表求解，我们将元素都存放在哈希表中，然后遍历哈希表，如果存在某个元素的个数大于数组长度的一半，那么说明该元素是主要元素。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> m;
        for (int x : nums) m[x]++;
        for (auto p : m) if (p.second > nums.size() / 2) return p.first;
        return -1;
    }
};

摩尔投票法

这个题目的最优解是摩尔投票法，是一种特殊算法，其思想是主要元素的个数超过其他所有元素之和，因此用一个计数器记录当前获胜者的票数。

如果当前获胜者是A，票数是k，如果下一个选票是B，那么k–，如果下一个选票是A，那么k++。一旦k=0，就没有获胜者。最后投票完成后，如果存在主要元素，那么获胜者一定是主要元素。如果不存在主要元素，获胜者可能是其他元素。

如何理解呢？假设A是主要元素，那么A的选票足以大于其他的所有人，因此无论如何抵消，A都会在最后胜出。因此我们可以用一次遍历确定获胜者，然后再用一次遍历统计获胜者的票数即可。如果票数大于数组长度的一半则为主要元素，否则没有主要元素。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major, cnt = 0;
        for (int x : nums) {
            if (cnt == 0) {
                major = x;
                cnt++;
            }
            else cnt += major == x ? 1 : -1;
        }
        cnt = 0;
        for (int x : nums) if (x == major) cnt++;
        return cnt > nums.size() / 2 ? major : -1;
    }
};

刷题总结

这个题目难度很小，想给小伙伴们多科普一些特殊算法，拓展视野。