时间戳

首页 > 解决方案 > 检查 N > 2 个具有最高性能的数组之间的相等性？

javascript - 检查 N > 2 个具有最高性能的数组之间的相等性？

问题描述

我想检查n数组是否在 JavaScript 中都包含相同的整数？最有效的方法是什么？

标签： javascriptarraysequality

解决方案

该解决方案避免使用sort，使算法 O(n²)，其中 n 是数组的数量和长度。它具有不改变数组的额外好处，还可以让您传递包含任何类型的数组，而不仅仅是数字。它通过为每个数组项计算一个频率包来操作，然后评估它们是否都包含相同的数据。和函数都是 O(n) toBag。bagsEqual这使得主要算法arraysSameO(n²)。使用sort频率袋代替频率袋会得到 O(n²log(n)) 的解决方案，这几乎没有那么有利。

function arraysSame(...arrays) {
  if(arrays.length < 2) return true;

  let bag1 = toBag(arrays[0]);
  for(let i = 1; i < arrays.length; i++) {
    const bag2 = toBag(arrays[i]);
    if(!bagsEqual(bag1, bag2)) return false;
  }

  return true;
}

function bagsEqual(bag1, bag2) {
  if(bag1.size != bag2.size) return false;

  for(const [key, value] of bag1) {
    if(!bag2.has(key)) return false;
    if(value != bag2.get(key)) return false;
  }

  return true;
}

function toBag(array) {
  const bag = new Map();

  for(const val of array) {
    const count = bag.get(val) || 0;
    bag.set(val, count + 1);
  }

  return bag;
}

推荐阅读