比较两个数组中元素的相等性

Question

我有一个作业，需要检查两个整数数组（未排序）是否：

1. 长度相同
2. 第一个数组的元素包含整数，并且第二个数组包含任意顺序的相同值的平方。

例如：

test([5,4,1], [1,16,25]) // would return true ..

我目前所做的是首先将两个输入数组进行排序，然后比较它们的长度。一旦确定长度相同，我们就会迭代每个值以确保它们相等。请注意，因为我的循环没有给我预期的结果，所以我还没有开始将值与它们的平方对应项进行比较。以下是代码：

function test(arr1, arr2){
  // sort arrays
  const arr1Sort = arr1.sort(),
        arr2Sort = arr2.sort();

  // compare length and then compare values
  if(arr1Sort.length === arr2Sort.length) {
    for(let i = 0; i < arr1Sort.length; i++) {
      if(arr1Sort[i] === arr2Sort[i]) {
        return true;
      } else {
        return false;
      }
    }
  }
}

console.log(test([1,2,3], [1,5,4])); returns true but the array values are different?!

- exception-io

---

如果不相等，则将if反转，并在仅在整个数组通过时返回true。 - jonathan Heindl

如果它们的长度不同，也立即将长度比较反转并返回false。 - jonathan Heindl

输入数组中允许有重复数字吗？ - CertainPerformance

@CertainPerformance：是的，允许重复数字。谢谢！ - exception-io

Answer 1

在for循环中，无论if或else是否被满足，函数都会在第一个迭代上立即返回true或false - 它永远不会超过索引0。首先，在循环结束后才返回true，如果arr1Sort[i] ** 2 !== arr2Sort[i]则返回false（检查第一个平方是否等于第二个）。

此外，在排序时，请确保使用回调函数来比较每个项的差异，否则.sort将按字典顺序排序（例如，[1,11,2]）。

function comp(arr1, arr2){
  // sort arrays
  const sortCb = (a, b) => a - b;
  const arr1Sort = arr1.sort(sortCb),
      arr2Sort = arr2.sort(sortCb);

  // compare length and then compare values
  if(arr1Sort.length !== arr2Sort.length) {
    return false;
  }
  for(let i = 0; i < arr1Sort.length; i++) {
    if(arr1Sort[i] ** 2 !== arr2Sort[i]) {
      return false;
    }
  }
  return true;
}

console.log(comp([1,2,3], [1,5,4]));
console.log(comp([5,4,1], [1,16,25]));

您可以通过将arr2事先转换为一个由平方数索引的对象，从而将计算复杂度降低到O(N)而不是O(N log N)：

function comp(arr1, arr2){
  if (arr1.length !== arr2.length) {
    return false;
  }
  const arr2Obj = arr2.reduce((a, num) => {
    a[num] = (a[num] || 0) + 1;
    return a;
  }, {});
  for (let i = 0; i < arr1.length; i++) {
    const sq = arr1[i] ** 2;
    if (!arr2Obj[sq]) {
      return false;
    }
    arr2Obj[sq]--;
  }
  return true;
}

console.log(comp([1,2,3], [1,5,4]));
console.log(comp([5,4,1], [1,16,25]));

（如果不允许重复项，使用Set会更容易处理，但不幸的是允许重复项）

- CertainPerformance

---

非常棒的答案..完全有道理，谢谢！我有点想到这种情况，只是不知道如何在循环完成后返回true，这向我展示了如何做到，太完美了！ - exception-io

是我还是第一个答案在输入无序的情况下不起作用？ - exception-io

它在我的电脑上运行正常，使用 comp([5,4,1], [25,1,16])，你能给个例子吗？ - CertainPerformance

我认为这是因为.sort()没有回调函数（它按字典顺序比较），需要更改以检查比较的两个项之间的差异。 - CertainPerformance

非常好，按预期工作！因此，在这种情况下，我们需要为.sort()提供回调函数。 - exception-io

Answer 2

这应该可以工作，无论要比较的数据是什么：

function similar(needle, haystack, exact){
  if(needle === haystack){
    return true;
  }
  if(needle instanceof Date && haystack instanceof Date){
    return needle.getTime() === haystack.getTime();
  }
  if(!needle || !haystack || (typeof needle !== 'object' && typeof haystack !== 'object')){
    return needle === haystack;
  }
  if(needle === null || needle === undefined || haystack === null || haystack === undefined || needle.prototype !== haystack.prototype){
    return false;
  }
  var keys = Object.keys(needle);
  if(exact && keys.length !== Object.keys(haystack).length){
    return false;
  }
  return keys.every(function(k){
    return similar(needle[k], haystack[k]);
  });
}
console.log(similar(['a', {cool:'stuff', yes:1}, 7], ['a', {cool:'stuff', yes:1}, 7], true));
// not exact
console.log(similar(['a', {cool:'stuff', yes:1}, 7], ['a', {cool:'stuff', stuff:'more', yes:1}, 7, 'more stuff only at the end for numeric array']));

- StackSlave