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

Question

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

例如，在以下数组中：

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

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

- vise

---

你可以从这个Stackoverflow问题中借鉴一些想法。https://dev59.com/eXRA5IYBdhLWcg3wvgsb - Nosredna

我没有仔细阅读解决方案，但它们中是否有任何一种考虑了以下细微差别（优化？），基于仅需确定哪个元素具有最多出现次数的要求，而不是最多出现次数是多少...当循环数组时，如果计数可以停止，则差异在最高和次高出现次数之间小于剩余要循环的元素数量，循环可以停止，当前最高值将是最高值。 - Dexygen

这是一个与编程语言无关的问题，位于算法-在大型单词序列中查找前K个频繁单词的最有效方法-堆栈溢出。 - user202729

Answer 1

这只是一种模式，这里是一个快速但未经过优化的解决方案。它应该是O(n)。

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

- Matthew Flaschen

---

不错...但它只适用于字符串 - 不一定是限制，但需要考虑。 - James

我已经添加了一个版本的该算法以处理并列情况。 - samandmoore

我必须将f（modeMap [el] == null）替换为if（！modeMap [el]），因为在传递[2,3,3]时，modeMap [el]是未定义而不是null，导致出现奇怪的数字问题。 - Naz

我认为设置一个平局处理者是有道理的，这种情况下可以选取数组中出现顺序在前的元素作为获胜者。但你可以很容易地修改这个算法来得到所有并列最多的元素。 - Wylliam Judd

@seveneights nodeMap 是一个 JavaScript 对象，可以实现为 B 树。当它被实现为"O(1)" 哈希表时，引擎并不知道 nodeMap 的大小，所以必须重新分配内存。每次重新分配内存都需要花费 log N 的时间，因此最终 O(n log n) 仍然是一个准确的描述。无论哪种方式，log N 因素太小，在大多数情况下并不重要。 - noɥʇʎԀʎzɐɹƆ

Answer 2

自2009年以来，JavaScript已经有一些发展 - 我想再添加另一个选项。 我不太关心效率，直到实际出现问题，因此我对"优雅"代码的定义（如OP所规定）更偏向于可读性 - 当然这是主观的...

function mode(arr){
    return arr.sort((a,b) =>
          arr.filter(v => v===a).length
        - arr.filter(v => v===b).length
    ).pop();
}

mode(['pear', 'apple', 'orange', 'apple']); // apple

在这个特定的例子中，如果集合中有两个或多个元素出现次数相同，则返回数组中最后出现的那个。值得注意的是，它会修改您的原始数组 - 如果您事先使用 Array.slice 调用可以避免这种情况。

---

编辑：使用了一些 ES6 箭头函数 来更新示例，因为发生了 2015 并且我觉得它们看起来很漂亮... 如果您关心向后兼容性，可以在 修订历史记录 中找到旧版本的代码。

- Emissary

---

如果这不是优雅的代码，我就不知道什么是了。它就像函数式编程的广告。 - Sam H.

注意，arr将被修改（排序）。建议更改为：return [...arr].sort()。 - Daniel Pérez Rada

您的意思是“优雅”指的是“简洁”。因为这段代码是不必要的低效率，它在循环中重复调用整个数组的.filter函数，导致时间复杂度达到O(n * n * log(n))，而本应该是O(n)的算法。我认为“优雅”的解决方案应该是简洁、可维护、易读和高效的。 - ggorlen

没问题，但是你可能需要考虑删除你的评论，以免人们看到+15，误以为可以在实际的代码库中使用这个。不过，72个赞是主要的问题，很难或者不可能反驳。 - ggorlen

这并未考虑两个字符串具有相同频率的情况。mode(['pear', 'apple', 'orange', 'apple', 'pear']); // 梨 - Flavio

Answer 3

根据George Jempty的要求，让算法考虑并列情况，我提出了Matthew Flaschen算法的修改版。

function modeString(array) {
  if (array.length == 0) return null;

  var modeMap = {},
    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];
    } else if (modeMap[el] == maxCount) {
      maxEl += "&" + el;
      maxCount = modeMap[el];
    }
  }
  return maxEl;
}

现在将返回一个由&符号分隔的众数元素字符串。当接收到结果时，可以在该&元素上进行拆分，从而得到您的模式。

另一个选项是返回一个模式元素数组，如下所示：

function modeArray(array) {
  if (array.length == 0) return null;
  var modeMap = {},
    maxCount = 1,
    modes = [];

  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) {
      modes = [el];
      maxCount = modeMap[el];
    } else if (modeMap[el] == maxCount) {
      modes.push(el);
      maxCount = modeMap[el];
    }
  }
  return modes;
}

在上面的示例中，您现在可以将函数的结果处理为模式数组。

- samandmoore

---

在第二个例子中（数组那个），你不需要将modes设置为[array[0]]作为初始值。这会确保你在modes中有重复项。 这应该可以解决问题：var modes = []。 - vdclouis

这很棒！然而，当我使用一个包含两个不同值的数组进行测试时，它会返回数组中的第一个项目两次。不确定为什么会发生这种情况... - Crystal

@xgrioux 根据vdclouis的建议进行更改以解决此错误。即将[array[0]]更改为[ ]。 - Dave Haigh

建议将 == 实例更改为 ===，以强制执行严格相等。 - Len Joseph

第二个例子的细节：如果数组完全由单个项组成，则会返回相同的数组。如果您希望返回一个空数组，以便告诉您的代码没有比其他元素更频繁的元素，请将“else if（modeMap [el] == maxCount）”条件修改为“else if（modeMap [el] == maxCount && maxCount> 1）”。 - Giampaolo Ferradini

但是如果有两个值出现的次数相同，会发生什么？ - Bill Bronson

Answer 4

基于 Emissary 的 ES6+ 回答，你可以使用 Array.prototype.reduce 来进行比较（而不是排序、弹出和可能会改变数组的元素），我认为这看起来非常简洁。

const mode = (myArray) =>
  myArray.reduce(
    (a,b,i,arr)=>
     (arr.filter(v=>v===a).length>=arr.filter(v=>v===b).length?a:b),
    null)

我默认为null，如果你正在过滤null作为可能的选项，这不会始终给出真实的响应，也许这可以成为一个可选的第二个参数。

与其他各种解决方案一样，缺点是它无法处理“绘制状态”，但是稍微复杂一些的reduce函数仍然可以实现这一点。

- davidsharp

---

另一个缺点是这对于应该是线性操作的内容来说过于二次了。 - ggorlen

@ggorlen同意，性能不佳，请查看我的基准测试https://stackoverflow.com/a/77210052/14098260 - undefined

Answer 5

a=['pear', 'apple', 'orange', 'apple'];
b={};
max='', maxi=0;
for(let k of a) {
  if(b[k]) b[k]++; else b[k]=1;
  if(maxi < b[k]) { max=k; maxi=b[k] }
}

- Thinker

---

这仍然是O(n)，但它不必要地使用了两次遍历。 - Matthew Flaschen

由于 JavaScript 是通过传输的，因此看到小型解决方案总是很有趣。 - Nosredna

每次访问b，至少需要log(len(b))的时间，因此O(n)可能有点乐观。 - Nicolas78

代码中包含语法错误且无法运行，却获得了4个赞？这段代码只查看属性名称，而不是值。简洁本身是毫无意义的。如果代码失败了，那就更加如此。 - RobG

这会在窗口中污染全局变量，并且不必要地使代码混乱/难以阅读。没有提供代码如何工作或为什么它是一个好的解决方案的解释或描述。 - ggorlen

Answer 6

我将这个函数用作面试官的测试题，以下是我的解决方案：

const highest = arr => (arr || []).reduce( ( acc, el ) => {
  acc.k[el] = acc.k[el] ? acc.k[el] + 1 : 1
  acc.max = acc.max ? acc.max < acc.k[el] ? el : acc.max : el
  return acc  
}, { k:{} }).max

const test = [0,1,2,3,4,2,3,1,0,3,2,2,2,3,3,2]
console.log(highest(test))

- perusopersonale

---

这看起来是这里最好的答案，但我得到了“无法读取未定义的reduce.k属性”（在您的解决方案中的第2行）。有什么想法吗？ - Brian Patterson

没事了，我把错误的变量名放错位置了。是我的错。我觉得这个代码还不错，虽然我还没有让它正常工作哈哈。 - Brian Patterson

Answer 7

尝试使用声明性方法。该解决方案建立了一个对象，以记录每个单词的出现次数。然后通过将每个单词的总出现次数与对象中发现的最高值进行比较，将对象过滤为数组。

const arr = ['hello', 'world', 'hello', 'again'];

const tally = (acc, x) => { 

  if (! acc[x]) { 
    acc[x] = 1;
    return acc;
  } 

  acc[x] += 1;
  return acc;
};

const totals = arr.reduce(tally, {});

const keys = Object.keys(totals);

const values = keys.map(x => totals[x]);

const results = keys.filter(x => totals[x] === Math.max(...values));

- Corey Clark

---

请解释您的答案。 - Haris

我会避免在过滤循环中计算最大值并删除键到值的映射语句。虽然这个答案不是最有效的，但它比在Reducer中过滤要好，并且在我看来易读明了。const maxValue = Math.max(...Object.values(totals)); const results = keys.filter(x => totals[x] === maxValue); - milesaron

Answer 8

这个解决方案的复杂度为 O(n)：

function findhighestOccurenceAndNum(a) {
  let obj = {};
  let maxNum, maxVal;
  for (let v of a) {
    obj[v] = ++obj[v] || 1;
    if (maxVal === undefined || obj[v] > maxVal) {
      maxNum = v;
      maxVal = obj[v];
    }
  }
  console.log(maxNum + ' has max value = ' + maxVal);
}

findhighestOccurenceAndNum(['pear', 'apple', 'orange', 'apple']);

- Gorakh Nath

Answer 9

这是使用内置地图的现代版本（因此适用于更多不能转换为唯一字符串的东西）：

'use strict';

const histogram = iterable => {
    const result = new Map();

    for (const x of iterable) {
        result.set(x, (result.get(x) || 0) + 1);
    }

    return result;
};

const mostCommon = iterable => {
    let maxCount = 0;
    let maxKey;

    for (const [key, count] of histogram(iterable)) {
        if (count > maxCount) {
            maxCount = count;
            maxKey = key;
        }
    }

    return maxKey;
};

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

- Ry-

---

如果在TypeScript中使用，请使用Array.from()将histogram(iterable)进行包装：https://github.com/microsoft/TypeScript/issues/11209#issuecomment-303152976 - sMyles

Answer 10

为了让代码易于阅读和维护，我分享以下内容:

function getMaxOcurrences(arr = []) {
  let item = arr[0];
  let ocurrencesMap = {};

  for (let i in arr) {
    const current = arr[i];

    if (ocurrencesMap[current]) ocurrencesMap[current]++;
    else ocurrencesMap[current] = 1;

    if (ocurrencesMap[item] < ocurrencesMap[current]) item = current;
  }

  return { 
    item: item, 
    ocurrences: ocurrencesMap[item]
  };
}

希望它能帮助到某些人 ;)！

- Eliecer Chicott