我用两行代码搞定了，结果妹子有更巧妙的办法

在线认输。

自从我把妹子的学习之心给引起来之后，她的学习热情再也没下去过。这不，大早上就来找阿粉讨论算法。

妹子：小哥哥，我给你出个题啊

阿粉：来，我就不信能难到我

妹子：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。比如：数组 [3，2，3] 的多数元素是 3 ，数组 [2，2，1，1，1，2，2] 的多数元素是 2 。怎么样，可以答出来嘛？

阿粉：可真是小看我了。

阿粉略微思考了一下，既然多数元素在数组中出现的次数大于 ⌊ n/2 ⌋ ，我给这个数组排个序，然后取中间的值，得到的肯定就是多数元素，要不然不符合题意。

这样的话，两行代码就可以搞定：

Arrays.sort(nums);
return nums[nums.length >> 1];

阿粉写完程序之后，一运行一点儿毛病都没有，而且两行代码就搞定了，阿粉不由得骄傲起来

阿粉：小妹妹，我实现了，两行代码就搞定了。

妹子看了看，结果一脸嫌弃：你这样的代码简单是简单，但是时间复杂度是 O(nlogn) ，空间复杂度是 O(logn) ，应该还有更好的解决方案才对吧。

无奈阿粉的思路刚开始就是这样想的，所以怎么也想不到别的好办法了，就去请教妹子。

妹子：其实有个方案比你这个要好一点儿，就是摩尔投票法。咱们平时都是怎么投票的呢？大家每个人都选一个人写在纸条上，然后开始拆开纸团瞅瞅选的是谁。刚开始默认大家都是 0 票，然后纸条上投的是谁，这个人就多一票，最后看谁的票数比较多。回到咱们这个题目，既然是众数，而且出现的次数大于 ⌊ n/2 ⌋ ，那我们可以假设一个数就是要求的众数，同时设置这个数字出现的次数为 0 ，然后和接下来的数字进行比较。如果一样呢，咱们把这个数字出现的次数加上 1 ，如果不一样，就让次数减 1 ，当这个值减到 0 时，说明刚开始假设的数字不是众数，那就换当前的这个数字，继续循环。这样最后这个数字出现的次数一定是大于等于 0 的，要不然就不符合 出现的次数大于 ⌊ n/2 ⌋ 这个题意了，最后的最后，将真正的众数返回即可。

阿粉：你这么一说，就把我的思路打开了，你等下，我这就去实现。

// 设置初始票数为 0
int count = 0 ;
// 先将要求的众数定义为空
Integer majorityElement = null;
	// 循环数组
    for(int num : nums){
		// 当 count 为 0 时,假设当前的数为要求的众数
        if (count == 0){
            majorityElement = num;
        }
		// 当 num 等于假设的众数时, count 就加 1
        count += ( num == majorityElement ) ? 1 : -1 ;
    }
// 最后返回真正的众数
return majorityElement;

阿粉自己在内心小算盘了一下，发现这样的时间复杂度是 O(n) ，空间复杂度是 O(1) ，阿粉不由得在心里给妹子竖个大手指

让阿粉在线认输的操作，你会学会了嘛？