在一个数组中获取出现次数最高的元素

123

我正在寻找一种优雅的方法来确定JavaScript数组中出现率最高的元素(mode)。

例如,在以下数组中:

['pear', 'apple', 'orange', 'apple']

'apple'元素是最常见的一个。


你可以从这个Stackoverflow问题中借鉴一些想法。https://dev59.com/eXRA5IYBdhLWcg3wvgsb - Nosredna
我没有仔细阅读解决方案,但它们中是否有任何一种考虑了以下细微差别(优化?),基于仅需确定哪个元素具有最多出现次数的要求,而不是最多出现次数是多少...当循环数组时,如果计数可以停止,则差异在最高和次高出现次数之间小于剩余要循环的元素数量,循环可以停止,当前最高值将是最高值。 - Dexygen
这是一个与编程语言无关的问题,位于算法-在大型单词序列中查找前K个频繁单词的最有效方法-堆栈溢出 - user202729
44个回答

1
这是我的解决方案:-

function frequent(number){
    var count = 0;
    var sortedNumber = number.sort();
    var start = number[0], item;
    for(var i = 0 ;  i < sortedNumber.length; i++){
      if(start === sortedNumber[i] || sortedNumber[i] === sortedNumber[i+1]){
         item = sortedNumber[i]
      }
    }
    return item
  
}

   console.log( frequent(['pear', 'apple', 'orange', 'apple']))


不适用于更多的物品。 - undefined

1
这是我的解决方案:-

 const arr = [
2, 1, 10, 7, 10, 3, 10, 8, 7, 3, 10, 5, 4, 6, 7, 9, 2, 2, 2, 6, 3, 7, 6, 9, 8,
9, 10, 8, 8, 8, 4, 1, 9, 3, 4, 5, 8, 1, 9, 3, 2, 8, 1, 9, 6, 3, 9, 2, 3, 5, 3,
2, 7, 2, 5, 4, 5, 5, 8, 4, 6, 3, 9, 2, 3, 3, 10, 3, 3, 1, 4, 5, 4, 1, 5, 9, 6,
2, 3, 10, 9, 4, 3, 4, 5, 7, 2, 7, 2, 9, 8, 1, 8, 3, 3, 3, 3, 1, 1, 3,
];

function max(arr) {
let newObj = {};

arr.forEach((d, i) => {
    if (newObj[d] != undefined) {
        ++newObj[d];
    } else {
        newObj[d] = 0;
    }
});
let nwres = {};
for (let maxItem in newObj) {
    if (newObj[maxItem] == Math.max(...Object.values(newObj))) {
        nwres[maxItem] = newObj[maxItem];
    }
}
return nwres;
}


console.log(max(arr));


1

简单解决方案!

function mostFrequentElement(arr) {
    let res = [];
    for (let x of arr) {
        let count = 0;
        for (let i of arr) {
            if (i == x) {
                count++;
            }
        }
        res.push(count);
    }
    return arr[res.indexOf(Math.max(...res))];
}
array = [13 , 2 , 1 , 2 , 10 , 2 , 1 , 1 , 2 , 2];
let frequentElement = mostFrequentElement(array);
console.log(`The frequent element in ${array} is ${frequentElement}`);

循环遍历所有元素并收集数组中每个元素的计数是解决方案的核心思想。

1
使用ES6,您可以像这样链接方法:

    function findMostFrequent(arr) {
      return arr
        .reduce((acc, cur, ind, arr) => {
          if (arr.indexOf(cur) === ind) {
            return [...acc, [cur, 1]];
          } else {
            acc[acc.indexOf(acc.find(e => e[0] === cur))] = [
              cur,
              acc[acc.indexOf(acc.find(e => e[0] === cur))][1] + 1
            ];
            return acc;
          }
        }, [])
        .sort((a, b) => b[1] - a[1])
        .filter((cur, ind, arr) => cur[1] === arr[0][1])
        .map(cur => cur[0]);
    }
    
    console.log(findMostFrequent(['pear', 'apple', 'orange', 'apple']));
    console.log(findMostFrequent(['pear', 'apple', 'orange', 'apple', 'pear']));

如果两个元素具有相同的出现次数,它将返回这两个元素。并且它适用于任何类型的元素。

不应在已将变量arr定义为参数的作用域内使用该变量。这可能会导致根据所使用的浏览器而定的错误。 - mesqueeb
arr.indexOf(cur) 指的是哪个 arr?是在 reduce 函数中的顶层参数,还是函数内的参数? - mesqueeb

1
这是我处理它的方法,只需使用.filter

var arr = ['pear', 'apple', 'orange', 'apple'];

function dup(arrr) {
    let max = { item: 0, count: 0 };
    for (let i = 0; i < arrr.length; i++) {
        let arrOccurences = arrr.filter(item => { return item === arrr[i] }).length;
        if (arrOccurences > max.count) {
            max = { item: arrr[i], count: arrr.filter(item => { return item === arrr[i] }).length };
        }
    }
    return max.item;
}
console.log(dup(arr));


1
const mode = (str) => {
  return str
    .split(' ')
    .reduce((data, key) => {
      let counter = data.map[key] + 1 || 1
      data.map[key] = counter

      if (counter > data.counter) {
        data.counter = counter
        data.mode = key
      }

      return data
    }, {
      counter: 0,
      mode: null,
      map: {}
    })
    .mode
}

console.log(mode('the t-rex is the greatest of them all'))

1
我想到了一个更短的解决方案,但它使用了 lodash。适用于任何数据,而不仅仅是字符串。对于对象可以使用:
const mostFrequent = _.maxBy(Object.values(_.groupBy(inputArr, el => el.someUniqueProp)), arr => arr.length)[0];

这是关于字符串的内容:

const mostFrequent = _.maxBy(Object.values(_.groupBy(inputArr, el => el)), arr => arr.length)[0];

只需按照特定标准将数据分组,然后找到最大的组。

如果所有元素出现次数相等怎么办?在这种情况下,它将失败。 - YaSh Chaudhary
这就是为什么有一个 [0] - 取第一个的原因。如果出现次数相等,则返回第一个。如果有问题,请按大小检查下一个。 - Nicolae Lozovan

1
在许多情况下(记住其中的计数),Map 可以提供最佳性能。

const arr = ['pear', 'apple', 'orange', 'apple'];

const result = arr.reduce((r, item, curr) => (
    (curr = r.map.get(item)) && ++curr.count || r.map.set(item, curr = { item, count: 1 }),
    r.max.count < curr.count && (r.max = curr), r
), { map: new Map, max: { item: null, count: 0 } }).max.item;

console.log(result);

与拥有400个数组项的顶级解决方案进行基准测试:
` Chrome/117
--------------------------------------------------------------
Alexander            1.0x  |  x100000  342  347  349  349  355
Matthew Flaschen     2.1x  |  x100000  729  733  735  741  748
Emissary            33.3x  |    x1000  114  114  116  120  125
davidsharp         178.4x  |    x1000  610  611  612  616  621
--------------------------------------------------------------
https://github.com/silentmantra/benchmark `

const chunk = ['pear', 'apple', 'orange', 'apple'];
const arr = [];
let count = 100;
while(count--) arr.push(...chunk);

// @benchmark davidsharp
arr.reduce(
    (a,b,i,arr)=>
     (arr.filter(v=>v===a).length>=arr.filter(v=>v===b).length?a:b),
    null)

// @benchmark Matthew Flaschen
function mode(array)
{
    if(array.length == 0)
        return null;
    var modeMap = {};
    var maxEl = array[0], maxCount = 1;
    for(var i = 0; i < array.length; i++)
    {
        var el = array[i];
        if(modeMap[el] == null)
            modeMap[el] = 1;
        else
            modeMap[el]++;  
        if(modeMap[el] > maxCount)
        {
            maxEl = el;
            maxCount = modeMap[el];
        }
    }
    return maxEl;
}
// @run
mode(arr);

// @benchmark Emissary
arr.sort((a,b) =>
          arr.filter(v => v===a).length
        - arr.filter(v => v===b).length
    ).pop();

// @benchmark Alexander
arr.reduce((r, item, curr) => (
    (curr = r.map.get(item)) && ++curr.count || r.map.set(item, curr = { item, count: 1 }),
    r.max.count < curr.count && (r.max = curr), r
), { map: new Map, max: { item: null, count: 0 } }).max.item;

/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));


0
你可以尝试这个:
 // using splice()   
 // get the element with the highest occurence in an array
    function mc(a) {
      var us = [], l;
      // find all the unique elements in the array
      a.forEach(function (v) {
        if (us.indexOf(v) === -1) {
          us.push(v);
        }
      });
      l = us.length;
      while (true) {
        for (var i = 0; i < l; i ++) {
          if (a.indexOf(us[i]) === -1) {
            continue;
          } else if (a.indexOf(us[i]) != -1 && a.length > 1) {
            // just delete it once at a time
            a.splice(a.indexOf(us[i]), 1);
          } else {
            // default to last one
            return a[0];
          }
        }
      }
    }

// using string.match method
function su(a) {
    var s = a.join(),
            uelms = [],
            r = {},
            l,
            i,
            m;

    a.forEach(function (v) {
        if (uelms.indexOf(v) === -1) {
            uelms.push(v);
        }
    });

    l = uelms.length;

    // use match to calculate occurance times
    for (i = 0; i < l; i ++) {
        r[uelms[i]] = s.match(new RegExp(uelms[i], 'g')).length;
    }

    m = uelms[0];
    for (var p in r) {
        if (r[p] > r[m]) {
            m = p;
        } else {
            continue;
        }
    }

    return m;
}

0
function mode(array){
    var set = Array.from(new Set(array));
    var counts = set.map(a=>array.filter(b=>b==a).length);
    var indices = counts.map((a,b)=>Math.max(...counts)===a?b:0).filter(b=>b!==0);
    var mode = indices.map(a=>set[a]);
    return mode;
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接