题目描述：

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

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

题目非常简单，让我们找出现次数最多的数，使用Hash表应该是最好想到的，不多赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
//代码如下
	public int majorityElement(int[] nums) {
        if (nums.length <= 2) return nums[0];//特殊情况，直接返回
        HashMap<Integer, Integer> map = new HashMap<>(16);
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) map.put(nums[i], 1);//不存在创建添加
            else {
                map.put(nums[i], map.get(nums[i]) + 1);
                if (map.get(nums[i]) > nums.length / 2) return nums[i];
            }
        }
        return 0;
    }

空间复杂度优化（难度比较高，感觉有点像贪心）

但题目让我们尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。而上面的空间复杂度为 O(N)所以我们要优化，只用有限的变量去实现这个记录最大次数，也就是其他参数应该是“无状态的”，至少应该不需要我们去解决，笔者尝试几分钟并没找到解法，看答案才知道，所以给大家写一下我的理解以及怎样有可能能想到这些方法。

这里要用到的是摩尔投票的算法：
题目告诉我们有个数出现次数超过n/2，我们称它X，而所谓的算法就是指如果数据进行投票，非X则投反票，X投正票，最后的投票一定是正的。（投票本身不重要，重要的是思想，应该怎样量化这些数据）

如果我指定一个数作为基准，当经过一轮投票后为0，则这轮有一半为此数，但有两种情况：
数刚好就X，那无所谓，对最后的结果没影响
否则，那此时X可能在另外的数中，但对后面却不影响，因为最多失去一半X，但同时失去的还有一半其他数（由于X的次数已经限定了大于一半，甚至没有等于 233，所以这个分支不会出现在最后一轮）
据此我们可知，最后一轮我们的选择必定刚好就是X

1
2
3
4
5
6
7
8
9
10
11
//代码如下
	public int majorityElement3(int[] nums) {
        int x = 0;//每一轮假定的数
        int votes = 0;//量化其他数据
        for (int num : nums) {
            if (votes == 0) x = num;//如果为0 则开启下一轮
            votes += x == num ? 1 : -1; //数据进行投票
        }

        return x;
    }