javascript - 检查数组中唯一数的个数是否超过n

Question

正如标题所读，我需要检查数组中唯一条目的数量是否超过 n。
Array.prototype.some()似乎非常适合这里，因为它会立即停止在数组中循环，找到肯定的答案，所以，请不要建议过滤掉非唯一记录并测量结果数据集长度的方法因为性能在这里很重要。

到目前为止，我使用以下代码来检查是否有超过 n=2唯一编号:

const res = [1,1,2,1,1,3,1,1,4,1].some((e,_,s,n=2) => s.indexOf(e) != s.lastIndexOf(e) ? false : n-- ? false : true);

console.log(res);

.as-console-wrapper { min-height: 100%}

它返回 false虽然有，但显然有 3 个唯一数字(2,3,4)。

非常感谢您帮助找出我的(愚蠢的)错误。

p.s. 我正在寻找一个纯JS的解决方案

Answer 1

您可以使用 Map()将数组值作为映射键并将计数作为值。然后遍历映射值以查找唯一数字的计数。如果计数超过限制返回 true , 如果不返回 false .

时间复杂度为 O(n) .再好不过了O(n)因为必须访问数组中的每个数字才能找到唯一数字的计数。

var data = [1, 1, 2, 1, 1, 3, 1, 1, 4, 1];

function exceedsUniqueLimit(limit) {
  var map = new Map();

  for (let value of data) {
    const count = map.get(value);
    if (count) {
      map.set(value, count + 1);
    } else {
      map.set(value, 1);
    }
  }

  var uniqueNumbers = 0;

  for (let count of map.values()) {
    if (count === 1) {
      uniqueNumbers++;
    }

    if (uniqueNumbers > limit) {
      return true;
    }
  }

  return false;
}

console.log(exceedsUniqueLimit(2));