資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目要求假設(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 following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example, Consider the following matrix: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true.
假設(shè)存在這樣一個(gè)二維數(shù)組，該數(shù)組從左到右，從上到下均遞增，且下一行第一個(gè)值比上一行最后一個(gè)值大。要求從里面找到一個(gè)目標(biāo)值，存在則返回true，否則返回false
一維二分法熟悉二分法的知道，在一個(gè)有序的一維數(shù)組中，可以只用O(lgn)的時(shí)間復(fù)雜度就可以從中判讀出目標(biāo)值是否存在。我們可以先對(duì)第一列上的值進(jìn)行一次二分法遍歷，確定了行后再在行中進(jìn)行第二次的二分法遍歷?？傆?jì)的時(shí)間復(fù)雜度為O(lgn），代碼如下：
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
if(row==0){
return false;
}
int column = matrix[0].length;
if(column==0){
return false;
}
int leftPointer = 0, rightPointer=row-1;
while(leftPointer<=rightPointer){
int mid = (leftPointer+rightPointer) / 2;
if(matrix[mid][0]<=target && matrix[mid][column-1]>=target){
leftPointer = 0;
rightPointer = column-1;
while(leftPointer<=rightPointer){
int columnMid = (leftPointer + rightPointer) / 2;
if(matrix[mid][columnMid] == target){
return true;
}else if(matrix[mid][columnMid] < target){
rightPointer = columnMid-1;
}else{
leftPointer = columnMid + 1;
}
}
return false;
}else if(target
二維二分法
如何能之間在二維數(shù)組上使用二分法呢。其實(shí)只要我們找到相應(yīng)的左指針和右指針以及其對(duì)應(yīng)的中間位置上的值即可。其實(shí)這個(gè)二維數(shù)組完全可以看成一個(gè)連續(xù)的一維數(shù)組，位于二維數(shù)組[i,j]位置可以看成一維數(shù)組中下標(biāo)為[i*column+j].由此我們知道，左右指針對(duì)應(yīng)中間節(jié)點(diǎn)在二維數(shù)組的下標(biāo)為mid/column。代碼如下：
public boolean searchMatrix2(int[][] matrix, int target){
if(matrix==null || matrix.length==0 || matrix[0].length==0){
return false;
}
int row = matrix.length;
int column = matrix[0].length;
int left = 0;
int right = row*column-1;
while(left<=right){
int mid = (left + right) / 2;
int tempVal = matrix[mid/column][mid%column];
if(tempVal == target){
return true;
}else if(tempVal < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
想要了解更多開(kāi)發(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/67286.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í)當(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 t...
Problem Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). https://leetcode.com/static/i...s...
Problem You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D mat...
摘要：題目詳情這道題目要求我們對(duì)一個(gè)正方形矩陣進(jìn)行順時(shí)針度的翻轉(zhuǎn)。并且要求不聲明額外的空間，不能新建二維數(shù)組。輸入數(shù)組旋轉(zhuǎn)后的輸入數(shù)組想法這道題因?yàn)橐笤谖弧Ｋ晕覀冃枰业揭环N解法，使得每次操作都是交換兩個(gè)元素的位置，最后實(shí)現(xiàn)整個(gè)矩陣的旋轉(zhuǎn)。 題目詳情 You are given an n x n 2D matrix representing an image.Rotate the ima...
閱讀 2193·2021-11-19 09:55
閱讀 2657·2021-11-11 16:55
閱讀 3187·2021-09-28 09:36
閱讀 1955·2021-09-22 16:05
閱讀 3290·2019-08-30 15:53
閱讀 1815·2019-08-30 15:44
閱讀 2907·2019-08-29 13:10
閱讀 1351·2019-08-29 12:30
