精选留言(20)

• 
  zqing

  2018-10-27

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

  

   37
• 
  白雪红叶约

  2018-11-08

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

   4

   25
• 
  Quantum

  2018-10-30

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

   3

   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
• 
  Dionysus

  2018-12-10

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

  展开

  作者回复: 😀😀👍🏻

   1

   5
• 
  榨汁机2号

  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;
      }

  展开

  

   4
• 
  Olorin

  2018-11-24

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

  作者回复: Super nice!!

  

   4
• 
  bq

  2018-11-29

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

  

   3
• 
  Aliliin

  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-10

  1. 摩尔投票算法來解是不是比较合理？
  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
• 
  L_Ch

  2019-10-03

  log（n）的解法：长度为n的数组找大于数目大于n/2的数。相当找到第top(n/2)的那个元素，一定数目大于n/2的元素。

  

  
• 
  关

  2019-08-15

  这个题目用divide来做不太好做吧……？

  

  
• 
  🌙照常升起

  2019-06-08

  go语言版本
  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-28

  Java的treeMap处理这种情况很方便

  

  
• 
  zchfaq

  2019-02-24

  由于这道题已经限制一定存在众数，摩尔投票法是最优解，但一般做题是想不到这种技巧的

  

  
• 
  乘坐Tornado的线程魔...

  2019-02-10

  @ Geek_b07739 同意你的观点。个人觉得应该先排序。不过这样的话时间复杂度仍然是N*logN

  

  
• 
  Derek

  2019-02-08

  GO语言版本实现：
  
  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
  }

  展开

  

  
• 
  zixuan

  2018-10-30

  @岳 每次数组减少一半，一共就是2n，所以就是O(n)了.

  

  