找到對數字在C＃2維數組

Question

什麼快速的方法 發現對數字的2漁政陣列

我有這個陣列

int[,] numbers = new int[,] { { 5, 2 }, { 5, 1 }, { 5, 0 } , ........... }; 

我必須爲整數像x,y

我想返回這一對衝擊片雷管的索引陣列

在如果所述一對不存在retun假

謝謝

Answer 1

如果數組沒有排序，那麼您可以做的最好的是線性搜索 - 逐行，逐列，甚至是對角線。

如果數組中的任何一個維都是有序的，那麼您可以使用二分搜索。

如果數據是有序的並且符合某種分佈，則可以使用分佈關聯查找，該查找可能比二元搜索稍微高效。

Answer 2

如果數組是有序的，您可以使用二進制搜索。否則，你將不得不做一個線性搜索。

Answer 3

做二維數組的排序，然後使用二進制搜索。

Answer 4

「最快」是模糊的;最快寫入，還是最快執行？

您可以在無序列表中獲得最快的數據將是線性的，實際的最佳和最差情況將取決於輸入數據。一個無序列表上最快的整體很可能​​是：

var i = 0; 
foreach(var subarray in numbers) 
{ 
    if(subarray[0] == x && subarray[1] == y || subarray[0] == y && subarray[1] == x) 
    return i; 
    i++; 
} 

最好的情況是，第一個元素，以元素; 1個元素，2個相等比較。最糟糕的情況是它不在那裏; n個元素，n * 4個相等比較。

通過檢查子陣列是否至少有一個至少包含一個座標的元素，可以在不太可能找到匹配的情況下「快速失敗」。如果沒有，請不要去檢查完全匹配。這是最壞的情況，元素是最後一個，無序（n * 2個元素，n * 6個比較），但最好的情況是它不存在（n個元素，n * 2個比較，如果這種情況可能比以前好）。最後，「快速失敗」算法允許使用Linq來縮減您製作全套條件檢查的元素數量;首先查找至少具有一個座標的元素（最多需要兩次檢查），然後僅檢查那些與完全匹配的元素（最多四次檢查）。然後，您掃描數組以找到您找到的第一個元素，這是一個相對較快的參考檢查。

var result = numbers.Where(a=>a[0] == x || a[0] == y) 
    .Where(a=>a[0] == x && a[1] == y || a[0] == y && a[1] == x) 
    .FirstOrDefault(); 

if(result != null) return Array.IndexOf(numbers, result); 

最好的情況，它不存在（n個元素，n * 2比較）。只有稍微差一點的可能情況是，只有一個元素具有任一座標（n + 1個元素，n * 2 +（2或4）比較）。最糟糕的情況是，匹配是最後一個元素，無序，列表中的每個元素都有第一個座標是x或y（n * 3元素，n * 7比較，但在大多數實際數據中這是極其不可能的） 。平均情況將取決於具有至少一個座標作爲其第一個值的元素的數量。