Breeze‘s Blog

题目

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：输入：nums = [3,2,3]
输出：3

示例 2：输入：nums = [2,2,1,1,1,2,2]
输出：2

题解

方法一：排序取中

拿到这道题目，首先唤醒了我们的数学思维。按照题目要求，需要求出给定数组中出现次数大于n/2的元素，而且可以假定一定会有这样的元素在数组中存在。不妨对数组进行排序，如果一个元素的数量超过了n/2个，那么数组中间的元素必然是我们需要取得的那个众数元素。看代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int m = n/2;
        return nums[m];
    }
};

我们首先对数组进行排序，然后求出该数组的大小并且取得其最中间的那个元素，最终通过测试用例。方法一到此为止。

方法二：摩尔投票（Boyer-Moore）

对于这个数组，我们还能发现一个显然的数学性质：如果一个数组有大于一半的数相同，那么任意删去两个不同的数字，新数组还是会有相同的性质。基于这个事实，我们可以采用同归于尽的方式，从数组中任意去掉两个元素，直到最后取得一个简单的数组，从中取得我们需要的众数就是手到擒来了。看代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
};

代码中，我们定义了votes作为票数，x作为假设的众数，每出现一个x，则票数加1，每出现一个非x值，则票数减1，若票数归零，则放弃指针走过的所有数据，选取新的x值开始投票。直到最后出现遍历完数组投票仍为正数的元素x。确立他成为最重的答案。至此，方法二解释完毕。

写在最后

算法的编写常常与数学思维脱离不了关系，我们需要多考虑需要解决的问题的数学性质，从中抽象出一套用于解决问题的方法。