有效的方法來找到是什麼數組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) 

其結果，溶液由日誌陣列的尺寸的因素而不同。因此，爲了獲得最佳解決方案，請使用相應的算法對較小的數組進行排序。