class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } } beat 100% java users

实现了分治法python版运行可以有不错的性能（几十ms），C++版奇慢无比（1600ms）。发现原因在于count方法python进行线性时间遍历计数后对结果做了缓存：如数过的存入一个HashMap，重复计算只需常数时间读取。C++版中手动对count结果缓存即可得到16ms的性能。

排序之后取中间的值就可以了因为题目说肯定存在这样的数出现的次数大于n/2

请问一下，对于这种数组{1,2,2,3,3,3,4,4,4,2,2,1}来说，采用分治法得到的结果会是4，而不是全局最多的2，不是么？

可以达到O(n)而不用使用map。 class Solution { public: int majorityElement(vector<int>& nums) { int cnt = 0; int cur = 0; for (int n : nums) { if (cnt == 0) { cnt = 1; cur = n; } else if (n == cur) { cnt++; } else { cnt --; } } return cur; } };

摩尔投票法,O(n)的时间复杂度 public int majorityElement(int[] nums) { int num = 0; int count = 0; for(int n : nums){ if (count == 0) num = n; count = n == num ? ++count : --count; } return num; }

1. 摩尔投票算法來解是不是比较合理？ 2. 直接排序，然后return num[n/2]?

方法2，map中找最大的数为什么是一次操作？O(1)

从 map count 中得出最大的不是也要遍历一遍吗，所以这里也是O(n)吧？

大于二分之一这个前提很关键，不然没法儿用分治来直接做