算法設計搜索矩陣

Question

值這個問題不是一門功課，那只是出於個人興趣，主要我的好奇心

我的教授在課堂上談到這個問題的一小會兒，但他沒有」這件事談得很多。下面是問題：

給定一個m×n矩陣A，其整數元素分別沿水平方向和垂直方向排列。我需要開發一個遞歸程序來搜索一個查詢值a 是否在A.討論您的設計的時間複雜性。

所以我想了一會兒。我的第一種方法是檢查基本情況：第一個元素和最後一個元素

檢查，如果第一個元素>如果最後一個元素<項目

產品，我想找到

什麼項目檢查這是虛矩陣：（x可以是任何數字，但是這個矩陣是那種垂直和水平方向）

   first  x   x  x   x 
       x  x   x  x   x 
       x  x   mid  x   x 
       x  x   x  x   x 
       x  x   x  x   last 

後，我檢查基本情況，並確保「項」我想找到的是這個矩陣的範圍之內，我不知道是否從矩陣的「中」（如二分搜索）檢查是可以的。如果項目<中，則着重於左半部分。如果項目>中，然後專注於右半部分。

但是，然後我試圖讓一個矩陣像下面和我的「項目」是10

    1  2   3  4   5 
       2  4   7  8   9 
       3  6   10  11   12 

如果我按照我之前說的方式：因爲10比中間的「7」時，我專注於正確的部分。然後我檢查「8」，因爲10大於「8」，我搜索右邊的部分。但10是不是在正確的...

任何人都可以給我的想法或見解如何解決這個問題？非常感謝

Answer 1

從左下角開始（在您的示例中爲3）。

1. 如果當前值小於您正在搜索的值，則向右轉。
2. 如果當前值大於您正在搜索的值，請上去。
3. 如果當前值與您正在搜索的值相同，則返回true。
4. 如果你走出矩陣，返回false。

這是O(n + m)，其中n和m在你的矩陣行和列的數量。這是因爲在每一步都完全排除了整行或一列。

Answer 2

最佳解決方案時間是O(1)，並且只是使用散列表跟蹤矩陣中的哪些元素。如果空間有問題，也可以使用布隆過濾器。

但是，因爲它們已經排序，所以可能不值得添加所有機器。

問題所在尋找的解決方案我認爲是O(N)解決方案（其中矩陣的大小爲N x N）;從左上角到左下角到右下角，直到找到大於查詢的元素爲止。然後，通過向右上方蠕動來搜索「級別曲線」，每次執行比較，以查看是否超出或低於查詢範圍（以正確或上升爲準）。

，你可以考慮一下這款另一種方式是保持對每列c窗口lower_c <查詢< higher_c的軌道，從左到右。此窗口的尺寸始終爲2.