2018-10-27排序之后取中间的值就可以了因为题目说肯定存在这样的数出现的次数大于n/2 40
2018-11-08请问一下，对于这种数组{1,2,2,3,3,3,4,4,4,2,2,1}来说，采用分治法得到的结果会是4，而不是全局最多的2，不是么？ 4 25- 2018-10-30方法2，map中找最大的数为什么是一次操作？O(1) 4 8
2018-10-27可以达到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;
}
};展开 8
2019-02-01摩尔投票法,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;
}展开 5
2018-12-10class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
beat 100% java users展开作者回复: 😀😀👍🏻
1 5
2018-11-24实现了分治法python版运行可以有不错的性能（几十ms），C++版奇慢无比（1600ms）。发现原因在于count方法python进行线性时间遍历计数后对结果做了缓存：如数过的存入一个HashMap，重复计算只需常数时间读取。C++版中手动对count结果缓存即可得到16ms的性能。作者回复: Super nice!!
4
2018-11-29从 map count 中得出最大的不是也要遍历一遍吗，所以这里也是O(n)吧？ 3
2019-11-08利用PHP自带函数的方法和排序方法进行解决：
1、利用 PHP 自带的 数组中值出现的次数来解决。
function majorityElement($nums)
{
$majority = count($nums) / 2;
foreach (array_count_values($nums) as $key => $value) {
if ($value >= $majority) {
return $key;
}
}
}
2. 利用 排序的方法进行解决。
function majorityElement($nums)
{
sort($nums);
return $nums[count($nums) / 2];
}展开 1
2019-04-101. 摩尔投票算法來解是不是比较合理？
2. 直接排序，然后return num[n/2]? 1
2018-12-31突然想到了桶排序。用桶记录次数。然后再找到最大的次数。 1
2018-10-29分享下@jinlibao的分治算法
https://leetcode.com/problems/majority-element/discuss/177183/C++-Divide-and-conquer-O(N)-solution-(4-ms-beats-100)
1. 如果数组长度是奇数，找出与末尾数相等的总个数，个数大于n/2直接return;
2. 去掉末尾数，两两比较相等则放入新数组;
3. 递归调用，传入新数组;
这个分治算法较谭老师讲的一分为二更容易理解，也少了计数(count)判断的步骤；
这个算法妙就妙在抓住了4个数中必然有3个数相同，两两比较相等只会留下1个数就是结果，所以只要用分治思路将数组分到4个长度就能得到结果。
作者说时间复杂度是O(N)，但我怎么认为是O(NlogN)呢？覃老师给回复下。展开 1- 2020-01-02这个还有一个好方法，就是遇到同样数加1，不同减1，0的时候放入当前数。
2019-10-03log（n）的解法：长度为n的数组找大于数目大于n/2的数。相当找到第top(n/2)的那个元素，一定数目大于n/2的元素。
2019-08-15这个题目用divide来做不太好做吧……？
2019-06-08go语言版本
func majorityElement(nums []int) int {
count, current := 0, 0
for _, v := range nums {
if count == 0 {
current = v
count++
}else if(current == v) {
count++
}else{
count--
}
}
return current
}展开
2019-02-28Java的treeMap处理这种情况很方便- 2019-02-24由于这道题已经限制一定存在众数，摩尔投票法是最优解，但一般做题是想不到这种技巧的
2019-02-10@ Geek_b07739 同意你的观点。个人觉得应该先排序。不过这样的话时间复杂度仍然是N*logN
2019-02-08GO语言版本实现：
func majorityElement(nums []int) int {
hash_map := make(map[int]int)
for i := 0; i < len(nums); i++ {
hash_map[nums[i]]++
}
key := 0
value := 0
for k, v := range hash_map {
if v > value {
key = k
value = v
}
}
return key
}展开