來自兩個列表（或陣列）的匹配項目

我遇到了一個問題，希望我的工作可以縮減到以下內容：我有兩個List<int> s，我想查看是否有任何int s在ListA等於任何int在ListB。（它們可以是數組，如果這樣可以讓生活更輕鬆，但我認爲List<>有一些內置的魔法可能會有所幫助。）我確信這是一個LINQ友好的問題，但我在2.0中工作。來自兩個列表（或陣列）的匹配項目

我的解決方案至今，一直到foreach通過利斯塔，然後通過foreach數組listB，

foreach (int a in ListA) 
{ 
    foreach (int b in ListB) 
    { 
     if (a == b) 
     { 
      return true; 
     } 
    } 
}

這實際上是非常漂亮的，當他們每三個項目長，但現在他們是200長，他們經常不匹配，所以我們得到N^2比較的最壞情況。甚至有40,000次比較的速度非常快，但我認爲我可能會錯過一些東西，因爲N^2對於這個特殊問題似乎很天真。

謝謝！

來源

2009-01-07 dnord

隨着LINQ，這是微不足道的，因爲你可以調用Intersect extension method上Enumerable class給你兩個數組的交集：

var intersection = ListA.Intersect(ListB);

然而，這是設置路口，這意味着如果ListA和ListB沒有獨特的值，你不會得到任何副本。換句話說，如果你有以下：

var ListA = new [] { 0, 0, 1, 2, 3 }; 
var ListB = new [] { 0, 0, 0, 2 };

然後ListA.Intersect(ListB)生產：

{ 0, 2 }

如果您期望：

{ 0, 0, 2 }

然後你將不得不保持當您掃描兩個列表時，您自己的項目數和收益/遞減項。

首先，你要收集單個項目的列出了Dictionary<TKey, int>：

var countsOfA = ListA.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count());

從那裏，你可以掃描ListB並放置在列表中，當你在countsOfA遇到一個項目：

：

// The items that match. 
IList<int> matched = new List<int>(); 

// Scan 
foreach (int b in ListB) 
{ 
    // The count. 
    int count; 

    // If the item is found in a. 
    if (countsOfA.TryGetValue(b, out count)) 
    { 
     // This is positive. 
     Debug.Assert(count > 0); 

     // Add the item to the list. 
     matched.Add(b); 

     // Decrement the count. If 
     // 0, remove. 
     if (--count == 0) countsOfA.Remove(b); 
    } 
}

您可以在推遲執行，像這樣的擴展方法包裝這件事

注意，這兩種方法是（和我道歉，如果我在這裏屠宰大O符號）O(N + M)其中N是第一個數組中的項目數，並M是項目的第二陣列中的數。您必須僅掃描一次每個列表，並且假定獲取哈希代碼並在哈希代碼上執行查找是O(1)（常量）操作。

來源

2009-01-07 06:05:24 casperOne

如何使用BinarySearch方法而不是迭代內循環中的所有元素？

來源

2009-01-07 05:39:48 shahkalpesh

不是BinarySearch依靠被排序的列表嗎？ http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx – 2009-01-07 06:45:21

將整個ListA加載到一個HashSet實例中，然後在ListB中對HastSet測試foreach項：我確信這將是O（N）。

//untested code ahead 
HashSet<int> hashSet = new HashSet<int>(ListA); 
foreach (int i in ListB) 
{ 
    if (hashSet.Contains(i)) 
     return true; 
}

下面是一行同樣的事情：

return new HashSet<int>(ListA).Overlaps(ListB);

HashSet的不.NET 3.5的存在，所以在.NET 2.0中，您可以使用Dictionary<int,object>（而不是使用HashSet<int>），並且始終因爲您只對關鍵字感興趣，所以將它存儲爲字典中的對象/值。

來源

2009-01-07 05:43:38 ChrisW

直到.NET 3.5才引入Hashset。 – casperOne 2009-01-07 06:00:29

散亂一般不是一個壞主意。如果有必要實施一個並不困難。 – PolyThinker 2009-01-07 06:07:04

在這種情況下，使用.Net 2.0，您可以使用Dictionary 而不是HashSet（因爲您只對鍵感興趣，所以始終將null作爲對象/值存儲在Dictionary中）。 – ChrisW 2009-01-07 06:08:09

而不是通過每個列表迭代的，看看在List.Contains方法：

foreach (int a in ListA) 
{ 
    if (ListB.Contains(a)) 
    return true; 
}

來源

2009-01-07 05:53:51

克里斯給出的O通過散列（N）溶液。現在，根據常數因子（由於散列），可能值得考慮通過排序的O（N log（N））解決方案。根據您的使用情況，您可能會考慮幾種不同的變體。

排序數組listB（O（N日誌（N）），並使用搜索算法來解析在利斯塔每個元素（這又是O（N）* O（日誌（N）））。
排序兩者利斯塔和數組listB（O（N日誌（N）），並使用一個O（N）的算法，以這些列表比較爲重複。

如果兩個列表將要使用多於一次，第二種方法是優選的。

來源

2009-01-07 06:04:59 PolyThinker

來自兩個列表（或陣列）的匹配項目

回答

相關問題