資訊專欄INFORMATION COLUMN
摘要：代碼如下超時(shí)當(dāng)然了，這個(gè)方法不出意外，超時(shí)了思路二二分法查找我們采用二分法的思想，將矩陣分解為更小的矩陣從而每一次篩選確保能夠去除掉一個(gè)子矩陣范圍。從而我們可以將目標(biāo)值鎖定在左上方的子矩陣上。
題目要求
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.
假設(shè)存在這樣一個(gè)矩陣，該矩陣從左至右以及從上到下的值均為由小到大排列?，F(xiàn)在輸入一個(gè)目標(biāo)值，要求判斷該矩陣中是否存在該值。
思路一：暴力遞歸直觀的來(lái)看我們肯定會(huì)從左上角開始判斷，如果當(dāng)前的值比目標(biāo)值大，那么結(jié)束返回該值不存在，而如果當(dāng)前的值比目標(biāo)值小，則我們順著行或是列繼續(xù)查找。
代碼如下：
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);
}
//超時(shí)
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);
}
當(dāng)然了，這個(gè)方法不出意外，超時(shí)了~
思路二：二分法查找我們采用二分法的思想，將矩陣分解為更小的矩陣從而每一次篩選確保能夠去除掉一個(gè)子矩陣范圍。我們以題目中的矩陣作為例子：
找到當(dāng)前矩陣的中心下標(biāo)，這里即為matrix[2][2]上的9，鑒于目標(biāo)值5比9小，因此我們將矩陣分解為如下四塊，并排除掉右下角的子矩陣，然后在剩余的三個(gè)矩陣中繼續(xù)遍歷。
[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]
如果目標(biāo)值比當(dāng)前中心值更小，那么我們就可以排除左上角矩陣。
這個(gè)思路的代碼如下：
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);
}
}
思路三：換一個(gè)起點(diǎn)
當(dāng)我們從左上角開始遍歷時(shí)，我們會(huì)發(fā)現(xiàn)一次比較可以提供的信息實(shí)在是太少了。我們可以試著從左下角開始遍歷看看是否能夠提供更多的信息。還是以題目中給的矩陣作為例子：
從左下角比較的時(shí)，一旦目標(biāo)值比當(dāng)前值大，我們就將下標(biāo)向右移動(dòng)，一旦目標(biāo)值比當(dāng)前值小，我們就將下標(biāo)向上移動(dòng)。我們可以看見，因?yàn)閺淖笙陆情_始遍歷，那么每次的遍歷都確保了我們的值一定比當(dāng)前下標(biāo)左側(cè)的所有列的值大，也比當(dāng)前下標(biāo)下方所有行的值都大。從而我們可以將目標(biāo)值鎖定在左上方的子矩陣上。
這里給出的代碼是從右上角開始遍歷的，如下：
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;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70990.html
摘要：由于數(shù)組的特性，我們可以從二維數(shù)組的右上角出發(fā)，如果目標(biāo)小于該數(shù)，則向左移動(dòng)左邊的數(shù)字肯定更小，而當(dāng)前列中所有數(shù)字都比該數(shù)字大。 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...
摘要：題目要求假設(shè)存在這樣一個(gè)二維數(shù)組，該數(shù)組從左到右，從上到下均遞增，且下一行第一個(gè)值比上一行最后一個(gè)值大。總計(jì)的時(shí)間復(fù)雜度為，代碼如下二維二分法如何能之間在二維數(shù)組上使用二分法呢。 題目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the foll...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來(lái)覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來(lái)覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：兩種方法，轉(zhuǎn)置鏡像法和公式法。首先看轉(zhuǎn)置鏡像法原矩陣為轉(zhuǎn)置后水平鏡像翻轉(zhuǎn)后所以，基本的思路是兩次遍歷，第一次轉(zhuǎn)置，第二次水平鏡像翻轉(zhuǎn)變換列坐標(biāo)。公式法是應(yīng)用了一個(gè)翻轉(zhuǎn)的公式如此翻轉(zhuǎn)四次即可。二者均可，并無(wú)分別。 Problem You are given an n x n 2D matrix representing an image.Rotate the image by 90 de...
閱讀 3056·2021-11-22 12:06
閱讀 657·2021-09-03 10:29
閱讀 6632·2021-09-02 09:52
閱讀 2043·2019-08-30 15:52
閱讀 3447·2019-08-29 16:39
閱讀 1216·2019-08-29 15:35
閱讀 2096·2019-08-29 15:17
閱讀 1450·2019-08-29 11:17
