有效的方法来找到是什么数组A的元素数组b

Question

在我颗粒的情况下，我需要一个JavaScript代码，发现是什么数组a的字符串数组B.

但要问的一般问题它更有趣：

给定阵列A与N长度和阵列B，返回一个Boolean[]阵列长度的N使得Boolean[i]将是true IFF A[i]产品在B。

这个问题最有效的解决方案是什么？这两个数组都是未排序的，数组B可以是空的，它可以大于或小于数组A。

Answer 1

有几种不同的方法可以通过改变复杂性来做到这一点。

首先，您可以对这两个列表执行嵌套循环，并在B中找到相应的解决方案时，打印出A中的元素。这是O(ab)时间和O(1)空间。其次，您可以对两个列表进行排序，然后逐步浏览列表中的锁步，查找匹配（想象mergesort中的合并操作）。这是O(aloga + blogb)时间和O(1)或O(a+b)空间，具体取决于您是否要在原地进行排序。第三，您可以对第二个列表进行排序，然后在A中一次一个二进制搜索元素。这是O(blogb + alogb)时间和O(1)或O(b)空间，同样取决于您是否在原地进行排序。

Tosters提出了一种解决方案，您可以创建一个哈希集并对其进行重复查询。根据哈希集解决冲突的方式，这在最坏的情况下渐近地等于第一个或第三个解（底层桶可以是列表或二叉搜索树）。

Answer 2

将数组B转换为散列集合（或其他快速搜索的集合），然后在数组A的每个元素上循环并检查该元素是否存在于集合中。

Answer 3

这是非常容易的JS这样做，我不会把它的算法:)

A.map(x => B.includes(x)); 

Answer 4

的Tosters的答案是完美的随机输入。然而，既然你问了通用算法，我想到了下面的方法。

您需要搜索其他元素中的一个元素，因此需要对其中的一个元素进行排序以获得最佳解决方案。让我们考虑这两种情况。为了简单起见，我们用相同的字母表示它们的大小在描述步骤之后，我在括号内提到了时间复杂度。

排序B：

1. Sort B O(B log B). 
2. Iterate over each element of A and check if element exists in B, O(A log B) 
Time complexity: O(A log B) + O(B log B) = O((A+B) log B) 

分选：

1. Sort array A also maintaining original position in sorted array, O(A log A). 
2. Iterate on each element of B and find all A's containing B. Now iterate over each searched element to get original index and update Boolean array. Also keep a marker in sorted A that the element has been searched to avoid searching if same number appears again. O(B log A) 
Time complexity: O(A log A) + O(B log A) = O((A+B) log A) 

其结果，溶液由日志阵列的尺寸的因素而不同。因此，为了获得最佳解决方案，请使用相应的算法对较小的数组进行排序。