如何有效地比较 JavaScript 中的数组

在本文中，我将向您展示两种解决典型面试题的方法。第一种方案更直观，但效率较低。第二种方案引入了一个很棒的解题工具：频率计数器对象，它大大提高了效率。

阅读本文您将获得以下收获：

解决问题的框架
一种非常有用、高效的解决问题的技术
提高分析功能和改善性能的能力

我还为喜欢视频的朋友们制作了一个YouTube视频。如果您喜欢这个视频，可以考虑订阅我的频道。

问题

“编写一个名为“squared”的函数，它接受两个数组作为参数。如果数组中的每个值在第二个数组中都有其对应的平方，则该函数返回 true。这两个值的频率必须相同。”

-- 你的面试官

首先，我将向您展示解决问题的“简单”方法——更明显但效率不高的方法。

然后我会向你展示一种使用“频率计数器”来高效解决问题的方法。这在你的问题解决工具箱（你的大脑）中是一个非常便捷的技巧。

理解问题

问题解决101：在尝试编写解决方案之前，理解问题至关重要——提供一些示例以及我们期望的结果。然后，我们可以用这些示例进行测试，以确保我们的解决方案能够正确运行。

例子：

平方([1, 2, 3], [9, 1, 4]) // true
平方([1, 2, 3], [1, 4]) // false
平方([2, 2, 3], [4, 9, 9]) // false

例 1 是正确的，因为：

1 ² = 1（是的，它在数组 2 中）
2 ² = 4 （是的，它在数组 2 中）
3 ² = 9（是的，它在数组 2 中）

例 2 是错误的，因为：

1 ² = 1（是的，它在数组 2 中）
2 ² = 4 （是的，它在数组 2 中）
3 ² = 9（不，这不在数组 2 中）

例 3 是错误的，因为：

2 ² = 4（是的，它在数组 2 中）
2 ² = 4 （不，数组 2 中只有一个 4）
3 ² = 9（是的，但我们甚至不会进行此项检查，因为该函数事先返回了 false）

“天真”的方式

首先，我们检查数组的长度是否相等。如果不是，则返回 false 并提前退出函数，因为值的频率不可能相同。

接下来，我们循环遍历 arr1 中的每个数字 (num)。在循环内部，我们使用indexOf()来查找num2arr2 中的位置。将该值赋给变量foundIndex。

如果未找到该值，indexOf 将返回 -1。因此，我们可以检查 foundIndex 是否等于 -1，如果是，则返回 false。

如果一切顺利，我们继续使用该splice()方法从 arr2 中删除该值。这确保了两个数组中值的频率相同。

循环遍历每个数字，并且所有检查都通过后，我们就可以返回 true。

function squared(arr1, arr2) {
  if (arr1.length !== arr2.length) return false

  for (let num of arr1) {
    let foundIndex = arr2.indexOf(num ** 2)

    if (foundIndex === -1) return false

    arr2.splice(foundIndex, 1)
  }

  return true
}

表现

该算法具有Big O（n ²indexOf() ），因为我们循环遍历第一个数组中的每个项目，然后在此循环中，在最坏的情况下，我们循环遍历第二个数组中的每个项目（带有）。

如果你不知道（或者忘记了）什么是 Big O，请观看此视频：JavaScript 中的 Big O 符号。这是一个重要的话题！

如果数组长度为 n，则操作次数为 n * n = n ²。因此复杂度为 O(n ² )。

当然，这并不完全正确，因为第二个数组在每次循环后都会变短，所以平均而言，我们只会循环第二个数组的一半（0.5n）。大 O 将是 n * 0.5n = 0.5n² ^。但是大 O 着眼于全局，当输入趋近于无穷大时，0.5 就变得微不足道了，因此我们将其简化为大 O(n² ⁾。

更智能的方法 – 频率计数器对象 – Big O(n)

什么是频率计数器对象？

频率计数器是用来计数的物体。以下是两个它们适用场景的例子：

字符在字符串中出现的次数
数组中某个数字出现的次数

使用频率计数器还可以显著提高算法的性能，因为它通常可以消除使用嵌套 for 循环的需要。

以下是 [1, 2, 3, 4, 3] 的频率计数器对象：

let frequencyCounter = {
  1: 1,
  2: 1,
  3: 2,
  4: 1,
}

除 3 出现两次外，所有数字都出现一次。

解决方案

要创建频率计数器对象，我们需要循环遍历该数组。然后创建一个键，并赋予其当前值 + 1 的值；如果这是第一次遇到这个数字，则该值frequencyCounter[num]将为 undefined，因此我们将该值初始化为 1。

我使用了两个 for...of 循环，因为我觉得这样更容易阅读，但也可以只用一个 for 循环来完成。

然后可以比较频率计数器对象。我们首先检查频率计数器 1 的每个键的平方是否是频率计数器 2 的键。如果不是，则返回 false。

接下来，我们检查频率（值）是否相等。如果不相等，则返回 false。

如果我们毫发无损地度过这一切，我们就能找到真相并回归现实。

function squared(arr1, arr2) {
  if (arr1.length !== arr2.length) return false

  let frequencyCounter1 = {}
  let frequencyCounter2 = {}

  // Create frequencyCounter1
  for (let num of arr1) {
    frequencyCounter1[num] = frequencyCounter1[num] + 1 || 1
  }

  // Create frequencyCounter2
  for (let num of arr2) {
    frequencyCounter2[num] = frequencyCounter2[num] + 1 || 1
  }

  // Compare frequency counters
  for (let key in frequencyCounter1) {
    if (!(key ** 2 in frequencyCounter2)) return false

    if (frequencyCounter1[key] !== frequencyCounter2[key ** 2]) return false
  }

  return true
}

表现

为了创建频率计数器 1，我们循环遍历 arr1 中的所有数字 => n 个循环
与频率计数器2相同 => n 个循环
为了比较频率计数器，我们循环遍历频率计数器 1 中的所有键 => 在最坏的情况下，n 次循环

总计 = n + n + n = 3n

导致 Big O(n) – 线性时间复杂度。

比我们第一次尝试的 Big O(n ² )（二次时间复杂度）要好得多。

很棒的参考

我可以将我关于算法和数据结构的几乎所有知识归功于一门优秀的课程：Colt Steele 的 JavaScript 算法和数据结构大师班。
如果你喜欢书籍：JavaScript 数据结构和算法：理解和实现核心数据结构和算法基础的介绍（Sammie Bae 著）

如果您喜欢这篇文章，请考虑订阅我的 YouTube 频道- 我将非常感激！

谢谢阅读。

祝你有美好的一天！

文章来源：https://dev.to/doabledanny/how-to-compare-arrays-in-javascript-efficiently-1p0