劍指 offer 第一題： 二維數組中的查找

題目描述

在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

題目分析

圖 1

如果沒有頭緒的話，很顯然使用 暴力解法 是完全可以解決該問題的。

即遍歷二維數組中的每一個元素，時間複雜度：O(n^2)。

其實到這裡我們就可以發現，使用這種暴力解法並沒有充分利用題目給出的信息。這個二維數組是有特點的。

• 每一行都是遞增的
• 每一列都是遞增的

圖 2

解法

解法一：二分法

對於有序數組的查找問題而言，二分法是最容易想到的一個解法。

在這裡，對每一行使用二分查找，時間複雜度為 O(nlogn) 。二分查找複雜度 O(logn)，一共 n 行，所以是總體的時間複雜度是 O(nlogn) 。

解法二：規律法

根據二維數組由上到下，由左到右遞增的規律。

從左下角開始遍歷，如果當前值比 target 小則往右找，如果比 target 大則往上找，如果存在，必然可以找到目標數字。

即選取右上角或者左下角的元素 a[row] [col] 與 target 進行比較， 當target小於元素 a[row] [col] 時，那麼 target 必定在元素 a 所在行的左邊,讓 col-- ；當 target 大於元素 a[row] [col] 時，那麼 target 必定在元素 a 所在列的下邊,讓 row++ ；

圖 3

代碼如下：

public class Solution {
 public boolean Find(int target, int [][] array) {
 int row = 0;
 int col = array[0].length - 1;
 while(row <= array.length - 1 && col >= 0){
 if(target == array[row][col])
 return true;
 else if(target > array[row][col])
 row++ ;
 else
 col-- ;
 }
 return false;
 }
}

解法三：二分規律法

將解法一和解法二進行結合：對每行每列都使用二分查找，此時的時間複雜度為 O(logn * logm)。

圖 4

比如查找數字 9，首先使用用二分查找選出一行，總共有 5 行，那麼( 0 + 5 ) / 2 = 2，所以我們找出了第 2行為基準行。

圖 5

接下來對這一行（即第 2 行）又使用二分查找， 找出這一行（即第 2 行）中最後一個比目標值小的值，這裡是 6。

圖 6

6 及其所在的行和列把這個矩形劃分為 4 部分：

圖 7

1. 左上部分（圖 7 灰色部分），包括所在行的左邊部分和所在列的上邊部分：這一部分是絕對不會有目標數字的。因為這部分數字肯定比 6 小，而 6 又是小於目標數字的，所以左上部分全部小於目標數字。也就是說這個區域的數字不需要再進行判斷了。
2. 右下部分（圖 7 綠色部分），包括所在行的右邊部分，但不包括所在列的下面部分， 這一部分也是絕對不會有目標數字的。因為這部分都比 6 右邊的數字 11 大，而 11 又比目標數字 9 更大，所以右下部分全部都比目標數字大。也就是說這個區域的數字也不需要再進行判斷了。
3. 左下部分（圖 7 藍色部分），可能含有目標數字。
4. 右上部分（圖 7 棕色部分），可能含有目標數字。

這樣，實際上篩選的區域就只剩下

代碼如下：

public class Solution {
 public boolean Find(int target, int [][] array) {
 // 特殊情況處理
 if (array == null || array.length == 0 || array[0].length == 0) {
 return false;
 }
 int h = array.length - 1;
 int w = array[0].length - 1;
 // 如果目標值小於最小值 或者 目標值大於最大值，那肯定不存在
 if (array[0][0] > target || array[h][w] < target) {
 return false;
 }
 return binarySearchIn2DArray(array, target, 0, h, 0, w);
 }
 public static boolean binarySearchIn2DArray(int[][] array, int target, int startX, int endX, int startY, int endY) {
 if (startX > endX || startY > endY) {
 return false;
 }
 //首先，根據二分法找出中間行
 int x = (startX + endX) / 2;
 //對該行進行二分查找
 int result = binarySearch(array[x], target, startY, endY);
 //找到的值位於 x 行，result 列
 if (array[x][result] == target) {
 return true; // 如果找到則成功
 }
 //對剩餘的兩部分分別進行遞歸查找 

 return binarySearchIn2DArray(array, target, startX, x - 1, result + 1, endY)
 || binarySearchIn2DArray(array, target, x + 1, endX, startY, result);
 }
 public static int binarySearch(int[] array, int target, int start, int end) {
 int i = (start + end) / 2;
 if (array[i] == target || start > end) { 
 return i;
 } else if (array[i] > target) {
 return binarySearch(array, target, start, i - 1);
 } else {
 return binarySearch(array, target, i + 1, end);
 }
 }
}

閱讀更多 五分鐘學算法 的文章

關鍵字: 部分 return 數字