leetcode 240. Search a 2D Matrix II

lanffy 發布于2019-08-16 11:03 / 2783人閱讀

摘要：代碼如下超時當然了，這個方法不出意外，超時了思路二二分法查找我們采用二分法的思想，將矩陣分解為更小的矩陣從而每一次篩選確保能夠去除掉一個子矩陣范圍。從而我們可以將目標值鎖定在左上方的子矩陣上。

題目要求

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following 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]
]
Given target = 5, return true.

Given target = 20, return false.

假設存在這樣一個矩陣，該矩陣從左至右以及從上到下的值均為由小到大排列。現在輸入一個目標值，要求判斷該矩陣中是否存在該值。

思路一：暴力遞歸

直觀的來看我們肯定會從左上角開始判斷，如果當前的值比目標值大，那么結束返回該值不存在，而如果當前的值比目標值小，則我們順著行或是列繼續查找。
代碼如下：

    int column = 0;
    int row = 0;
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length == 0) return false;
        row = matrix.length;
        column = matrix[0].length;
        
        return searchMatrix2(matrix, target, 0, 0, row-1, column-1);
    }
    
    
    //超時
    public boolean searchMatrix(int rowIndex, int columnIndex, int target, int[][] matrix){
        if(rowIndex>=row || columnIndex>=column)return false;
        if(matrix[rowIndex][columnIndex] > target) return false;
        else if(matrix[rowIndex][columnIndex] == target) return true;
        return searchMatrix(rowIndex+1, columnIndex, target, matrix) || searchMatrix(rowIndex, columnIndex+1, target, matrix);
    }

當然了，這個方法不出意外，超時了~

思路二：二分法查找

我們采用二分法的思想，將矩陣分解為更小的矩陣從而每一次篩選確保能夠去除掉一個子矩陣范圍。我們以題目中的矩陣作為例子：

找到當前矩陣的中心下標，這里即為matrix[2][2]上的9，鑒于目標值5比9小，因此我們將矩陣分解為如下四塊，并排除掉右下角的子矩陣，然后在剩余的三個矩陣中繼續遍歷。

  [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]

如果目標值比當前中心值更小，那么我們就可以排除左上角矩陣。

這個思路的代碼如下：

    int column = 0;
    int row = 0;
    public boolean searchMatrix2(int[][] matrix, int target) {
        if(matrix==null || matrix.length == 0) return false;
        row = matrix.length;
        column = matrix[0].length;
        
        
        return searchMatrix2(matrix, target, 0, 0 ,row-1, column-1);
    }

    public boolean searchMatrix2(int[][] matrix, int target, int leftRow, int leftColumn, int rightRow, int rightColumn){
        if(leftRow==rightRow && leftColumn==rightColumn) return matrix[leftRow][leftColumn] == target;
        else if(leftRow > rightRow || leftColumn > rightColumn) return false;
        else if(target < matrix[leftRow][leftColumn] || target > matrix[rightRow][rightColumn]) return false;
        int midRow = (leftRow + rightRow) / 2;
        int midColumn = (leftColumn + rightColumn )/2;
        int midValue = matrix[midRow][midColumn];
        if(midValue == target) return true;
        else if(target < midValue){
            return searchMatrix2(matrix, target, leftRow, leftColumn, midRow-1, rightColumn) 
                    || searchMatrix2(matrix, target, midRow, leftColumn, rightRow, midColumn-1) ;
        }else{
            return searchMatrix2(matrix, target, leftRow, midColumn+1, rightRow, rightColumn)
                    || searchMatrix2(matrix, target, midRow+1, leftColumn, rightRow, midColumn);
        }
    }

思路三：換一個起點

當我們從左上角開始遍歷時，我們會發現一次比較可以提供的信息實在是太少了。我們可以試著從左下角開始遍歷看看是否能夠提供更多的信息。還是以題目中給的矩陣作為例子：

從左下角比較的時，一旦目標值比當前值大，我們就將下標向右移動，一旦目標值比當前值小，我們就將下標向上移動。我們可以看見，因為從左下角開始遍歷，那么每次的遍歷都確保了我們的值一定比當前下標左側的所有列的值大，也比當前下標下方所有行的值都大。從而我們可以將目標值鎖定在左上方的子矩陣上。

這里給出的代碼是從右上角開始遍歷的，如下：

    public boolean searchMatrix3(int[][] matrix, int target) {
        if(matrix == null || matrix.length < 1 || matrix[0].length <1) {
            return false;
        }
        int col = matrix[0].length-1;
        int row = 0;
        while(col >= 0 && row <= matrix.length-1) {
            if(target == matrix[row][col]) {
                return true;
            } else if(target < matrix[row][col]) {
                col--;
            } else if(target > matrix[row][col]) {
                row++;
            }
        }
        return false;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70990.html

[Leetcode] Search a 2D Matrix 搜索二維矩陣

摘要：由于數組的特性，我們可以從二維數組的右上角出發，如果目標小于該數，則向左移動左邊的數字肯定更小，而當前列中所有數字都比該數字大。 Search a 2D Matrix I Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following pr...

elisa.yang 2019-08-14 12:34 評論0 收藏0
leetcode74. Search a 2D Matrix

摘要：題目要求假設存在這樣一個二維數組，該數組從左到右，從上到下均遞增，且下一行第一個值比上一行最后一個值大。總計的時間復雜度為，代碼如下二維二分法如何能之間在二維數組上使用二分法呢。題目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the foll...

niuxiaowei111 2019-08-15 10:41 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LintCode/LeetCode] Rotate Image

摘要：兩種方法，轉置鏡像法和公式法。首先看轉置鏡像法原矩陣為轉置后水平鏡像翻轉后所以，基本的思路是兩次遍歷，第一次轉置，第二次水平鏡像翻轉變換列坐標。公式法是應用了一個翻轉的公式如此翻轉四次即可。二者均可，并無分別。 Problem You are given an n x n 2D matrix representing an image.Rotate the image by 90 de...

BenCHou 2019-08-14 15:22 評論0 收藏0