九章演算法 | Facebook面試題3 : Search a 2D Matrix II

撰文 | JZ

專欄 | 九章演算法

題目描述

在一個 m*n 整數矩陣中找到指定值 target。

這個整數矩陣有如下性質：

1. 每行從左到右數值遞增
2. 每列從上到下數值遞增

Example：

有如下矩陣：

指定值 target = 5，返回True。

指定值 target = 20，返回False。

解題思路分析

1. 簡單粗暴法：掃描整個矩陣，找出要找的指定值。演算法複雜度：O(m*n)。

2. 能不能優化？必須可以！根據矩陣的性質，會聯想到二分查找。要如何讓矩陣像數組那樣每次減少一部分不需要進行比較的呢？我們分析一下二分查找演算法，之所以每次可以捨棄掉一半，是因為我們通過中間的一個數（split_num）把數組分成了兩部分，左邊部分都不大於 split_num，右邊部分都不小於 split_num。然後通過比較 target 跟 split_num 的大小可以知道target在左邊還是右邊，從而捨棄掉另外一半。注意：切分後，左右兩部分跟切分前一樣都是一個數組，所以我們才能繼續按照同樣的標準對被選取的那一半進行處理。

1）現在數組變成了矩陣，要如何選取這個 split_num 呢？由於在數組中，我們取的是最中間的元素作為 split_num，那麼在這裡我們嘗試幾個處於矩陣中特殊位置、有可能切分矩陣的元素：

A. 矩陣中心位置：以上面為例，取 matrix[2][2] = 9 這個元素，若 target < 9 那麼 target 在左上角的這個矩陣里；但如果 target > 9，那麼 target 可能在 matrix[2][2] 的右邊，也可能在 matrix[2][2] 的下邊，這兩部分合起來形成一個類似 J 的形狀，並不是一個矩陣，那麼接下來我們便不能按照同樣的標準進行切分了。與上面說的二分查找演算法的想法相違背。

B. 矩陣對角線位置：如果是在對角線上任意取一個元素，那麼情況與上述一致，所以這個不可行。那嘗試對角線頂點元素？左上角 matrix[0][0] 和右下角 matrix[4][4] 的這兩個元素，因為是最小值和最大值，所以並不能起到切分的作用，同樣捨棄。而左下角 matrix[4][0] 和右上角 matrix[0][4] 這兩個元素呢？以左下角 matrix[4][0] = 18 為例，若 target < 18，那麼 target 在 matrix[4][0] 上方的這個矩陣里；若 target > 18，那麼 target 在 matrix[4][0] 右邊的這個矩陣里。不管 target 在哪一邊，被選取的那部分都是一個矩陣！那我們就能繼續在被選取的矩陣里比較其左下角元素和 target 的大小，進而繼續縮小 target 所在的矩陣，直到找到 target！(同理，右上角這個元素也是可行的。)

2） 由此，我們可以用「左下角元素」或「右上角元素」作為 split_num（我這裡就選擇了左下角元素）：

1. 如果 target == 左下角元素（當前位置），那麼已經完成任務！
2. 如果 target > 左下角元素 matrix[m][0]，那麼與 matrix[m][0] 同一列的元素全都小於 target， target 位於右邊的矩陣 matrix[0..m][1..n]。
3. 如果 target < 左下角元素 matrix[m][0]，那麼與 matrix[m][0] 同一行的元素全都大於 target， target 位於上邊的矩陣 matrix[0..m-1][0..n]。
4. 這個演算法的複雜度是 O(m+n)。

參考代碼

面試官角度分析

這道題如果能夠答案O(m+n)就可以拿到offer。

LintCode相關練習題

Search-a-2d-matrix

推薦閱讀：