找出数组中出现次数最多的元素（考虑性能优化）

Posted on   |  

今天被问到这么一个题。看上去挺简单的，利用object的key不能重复然后就把重复次数存下来了。。。
然后怎么找到最大的那个呢。。。。
然后怎么才能不遍历很多次呢。。。
然后如果既有Number又有string怎么办呢。。。
然后。。就跪了。。。

那就写一下把。。。

  • 只遍历一次
  • String(1) && Number(1)需要辨别成两个不同元素

只遍历了一次，时间复杂度是o(n), 只创建了一个map来存储，空间复杂度是o(1)
智力有限，只能优化到此了 =。=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function findMaxItem(arr){
  var max = null;
  var len = 0;
  var maxItem = null;
  var map = new Map();
  if(!Array.isArray(arr)){
    arr = Array.prototype.slice.call(arr);
  }

  arr.forEach((item)=>{
    // 已存在这个item，就把count++，然后与之前保存的max做比较
    // 如果大于之前的值，就是一个新的最大值，就把新的最大值和元素存下来
    if(map.has(item)){
      len = map.get(item);
      len ++;
      map.set(item, len);
      if(len > max){
        max = len;
        maxItem = item;
      }
    }else{
      // item和max都没有设置过，就是第一个元素咯
      if(max === null){
        max = 1;
        maxItem = item;
      }
      map.set(item, 1);
    }
  })
  console.log(`个数最多的值：${maxItem},有${max}个`);
}
findMaxItem([1111,1,1,1,1,2,4,'a',1,2,3,4,5,6,'a','a',1,'1'])
findMaxItem('aabbcccccccs');
findMaxItem(['hello','foo','foo','foo','bar','bar','12','12','12','12',12]);
findMaxItem([12,14,14,14,'14',5,5,33,5,2,3,55,5,5,14,4,14,3,14]);

好像没什么毛病了哇？
如果有两个不同的item都是一样的个数，并且都是最大的时候只会取一个的。
好像没什么毛病了哇？