5-多数元素

自己的做法

算法思想

使用map集合，key是数组元素，value是出现的次数。遍历整个数组，对于数组每个元素，查询map集合，如果存在，则将value + 1，如果不存在，则添加进map集合，并设value是1。

然后 遍历map集合，将value的值和数组一半元素一次比较，如果符合条件，则结束循环并输出。

代码实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> count;
        for(int i = 0; i < nums.size(); i++) {
            map<int, int>::iterator temp;
            if((temp = count.find(nums[i])) != count.end()) {
                temp->second++;
            } else {
                count.insert({nums[i], 1});
            }
        }
        //如果数组元素个数为偶数，则直接除2，奇数则+1除2
        int half = nums.size() % 2 == 0 ? (int)nums.size() / 2 : (int)(nums.size() + 1) / 2;
        int result = 0;
        for(map<int, int>::iterator i = count.begin(); i != count.end(); i++) {
            if(i->second >= half) {
                result = i->first;
                break;
            }
        }

        return result;

    }

};

性能分析

时间复杂度：遍历整个数组，所以是$O(n)$，n是数组元素个数。

空间复杂度：需要有一个map集合来存储元素，所以是$O(n)$。

官方做法

哈希表

算法思想

和我思路差不多，都使用哈希表来维护一个元素和出现次数关系的集合。在此基础上，这种做法在遍历数组时维护了一个最大值，所以在遍历完后，不需要遍历哈希表来查找多数元素。

算法实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

性能分析

同上。

时间复杂度$O(n)$，空间复杂度$O(n)$。

排序法

算法思想

首先将给定数组进行排序(从小到大，从大到小都可以)。则数组⌊$\frac{n}{2}$⌋位置一定是多数元素。

• 对于数组元素个数为偶数n，则多数元素至少出现n / 2，那么不论该多数元素是最大值还是最小值，排序后，$\frac{n}{2}$位置一定是该元素；则如果该多数元素介于最大值和最小值，则也一定会在n/2位置。

奇数同理。

算法实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {

        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];

    }

};

性能分析

时间复杂度：使用排序的默认实现，为$O(n*log{n})$。

空间复杂度：自己写排序算法，之需要使用$O(1)$空间，使用自带的排序算法，值传递，所以需要使用$O(logn)$的栈空间。

Boyer-Moore投票算法

算法思想

设置一个候选人cand_num，和该候选人出现的次数变量count。

候选人初始化为nums[0]，count初始化为1。

然后遍历该数组，遇到和cand_num相同的数，则count加1，否则count - 1。

然后判断count是否为0，如果为0，则更换候选人为当前数；否则继续循环。

循环结束，当前cand_num即是多数元素。

解释：

因为多数元素的个数 大于 $\frac{n}{2}$，若7个元素，则多数元素个数大于3，若8个元素，则多数元素个数大于4。

因此多数元素个数 - 其他所有元素个数 一定 大于等于 1。

相当于每一个多数元素和数组其他元素相抵消，最后至少还剩一个多数元素。

算法实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {

        int cand_num = nums[0], count = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] == cand_num) {
                count++;
            } else {
                count--;
            }
            if(count == 0) {
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;

    }

};

性能分析

时间复杂度：遍历整个数组，为$O(n)$。

空间复杂度：只使用了两个变量，为$O(1)$。