題目描述

編寫一個(gè)高效的算法來搜索 *m* x *n* 矩陣 matrix 中的一個(gè)目標(biāo)值 target 。該矩陣具有以下特性：

• 每行的元素從左到右升序排列。
• 每列的元素從上到下升序排列。

示例 1：

輸入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
輸出：true

示例 2：

輸入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
輸出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素從左到右升序排列
• 每列的所有元素從上到下升序排列
• -109 <= target <= 109

解法一

思路：

對(duì)矩陣按照中心點(diǎn)進(jìn)行分割，分成四個(gè)小的矩陣，在設(shè)置一個(gè)堆棧，堆棧每個(gè)元素是一個(gè)四維數(shù)組，記錄矩陣左上角坐標(biāo)和右下角坐標(biāo)。

如果target=matrix[rmiddle][cmiddle],則找到

如果target>matrix[rmiddle][cmiddle],則2，3，4子矩陣進(jìn)入堆棧

如果target<matrix[rmiddle][cmiddle],則1，2，3子矩陣進(jìn)入堆棧

代碼：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        Deque<int[]> stack = new ArrayDeque<>();
        int m = matrix.length, n = matrix[0].length;
        int leftRow=0, leftCol=0, rightRow=m-1, rightCol=n-1;
        int[] left2right={leftRow,leftCol,rightRow,rightCol};
        stack.push(left2right);
        while(!stack.isEmpty()) {

            //入棧問題
            int[] left2left = stack.pop();
            leftRow = left2left[0];leftCol = left2left[1];
            rightRow = left2left[2];rightCol = left2left[3];
            int rowMiddle = (leftRow + rightRow) / 2, colMiddle = (leftCol + rightCol) / 2;
            if (matrix[rowMiddle][colMiddle] == target) {
                return true;
            } else if (leftRow >= rightRow && leftCol >= rightCol) continue;
            else if (target < matrix[rowMiddle][colMiddle]) {
                stack.push(new int[]{leftRow, leftCol, rowMiddle, colMiddle});
                stack.push(new int[]{leftRow, colMiddle + 1, rowMiddle, rightCol});
                stack.push(new int[]{rowMiddle + 1, leftCol, rightRow, colMiddle});
            }else {
                stack.push(new int[]{leftRow, colMiddle + 1, rowMiddle, rightCol});
                stack.push(new int[]{rowMiddle + 1, leftCol, rightRow, colMiddle});
                stack.push(new int[]{rowMiddle + 1, colMiddle + 1, rightRow, rightCol});
            }
        }
        return false;
    }
}

解法二

思路：

對(duì)每行采用二分查找的方法。

代碼：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = search(row, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }

    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

解法三

思路：

來自官方解答。我們可以從矩陣 matrix 的右上角 (0,n?1) 進(jìn)行搜索。在每一步的搜索過程中，如果我們位于位置 (x,y)，那么我們希望在以 matrix 的左下角為左下角、以 (x,y) 為右上角的矩陣中進(jìn)行搜索，即行的范圍為 [x,m?1]，列的范圍為 [0,y]：

如果 matrix[x,y]=target，說明搜索完成；

如果 matrix[x,y]>target，由于每一列的元素都是升序排列的，那么在當(dāng)前的搜索矩陣中，所有位于第 y 列的元素都是嚴(yán)格大于 target 的，因此我們可以將它們?nèi)亢雎裕磳?code>y減少 1；

如果 matrix[x,y]<target，由于每一行的元素都是升序排列的，那么在當(dāng)前的搜索矩陣中，所有位于第 x 行的元素都是嚴(yán)格小于 target 的，因此我們可以將它們?nèi)亢雎裕磳?code> x 增加 1。

在搜索的過程中，如果我們超出了矩陣的邊界，那么說明矩陣中不存在 target。

可以將矩陣類比成一棵二叉排序樹，右上角是根節(jié)點(diǎn)，旁邊就是左右子樹。按照排序樹的查找方式進(jìn)行搜查。

代碼：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            } else {
                ++x;
            }
        }
        return false;
    }
}