資訊專(zhuān)欄INFORMATION COLUMN
摘要：由于數(shù)組的特性，我們可以從二維數(shù)組的右上角出發(fā)，如果目標(biāo)小于該數(shù)，則向左移動(dòng)左邊的數(shù)字肯定更小，而當(dāng)前列中所有數(shù)字都比該數(shù)字大。
Search a 2D Matrix I
二分法 復(fù)雜度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í)間 O(log(MN)) 空間 O(1)
思路我們可以把二維數(shù)組想象成一個(gè)一維數(shù)組，第一行尾連著第二行頭，第二行尾連著第三行頭...同樣是有個(gè)最小值最大值，二分得到中間值，通過(guò)對(duì)中間值取?？梢缘玫綄?duì)應(yīng)二維數(shù)組的下標(biāo)。這樣，該題就轉(zhuǎn)化為了一維有序數(shù)組二分搜索的題了。
注意二分搜索的幾個(gè)邊界條件是min<=max，min=mid+1,max=mid-1
代碼public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if(m == 0) return false;
int n = matrix[0].length;
int min = 0, max = m * n - 1;
while(min <= max){
int mid = min + (max - min) / 2;
int row = mid / n;
int col = mid % n;
if(matrix[row][col] == target){
return true;
} else if (matrix[row][col] < target){
min = mid + 1;
} else {
max = mid - 1;
}
}
return false;
}
}
2018/2
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not matrix[0]:
return False
rows = len(matrix)
cols = len(matrix[0])
min, max = 0, rows * cols - 1
while min <= max:
mid = min + (max - min) // 2
row = mid // cols
col = mid % cols
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
min = mid + 1
elif matrix[row][col] > target:
max = mid - 1
return False
Search a 2D Matrix II
貪心法 復(fù)雜度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í)間 O(N+M) 空間 O(1)
思路雖說(shuō)該方法叫貪心法不太得當(dāng)，但是貪心最能描述該方法的過(guò)程。由于數(shù)組的特性，我們可以從二維數(shù)組的右上角出發(fā)，如果目標(biāo)小于該數(shù)，則向左移動(dòng)（左邊的數(shù)字肯定更小，而當(dāng)前列中所有數(shù)字都比該數(shù)字大）。如果該數(shù)比目標(biāo)小，則向下移動(dòng)（下邊的數(shù)字肯定更大，而當(dāng)前行的所有數(shù)字逗比該數(shù)字?。?。這樣反復(fù)重復(fù)該過(guò)程就能找到目標(biāo)數(shù)。如果直到左下角都沒(méi)有該數(shù)，說(shuō)明找不到該數(shù)。同樣的，這題也可以從左下角向右上角尋找。
代碼public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0){
return false;
}
int i = 0, j = matrix[0].length - 1;
while(i < matrix.length && j >= 0){
int curr = matrix[i][j];
if(curr == target){
return true;
// 比目標(biāo)小則向下
} else if(curr > target){
j--;
// 比目標(biāo)大則向左
} else {
i++;
}
}
return false;
}
}
2018/2
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not matrix[0]:
return False
rows = len(matrix)
cols = len(matrix[0])
row, col = 0, cols - 1
while row >= 0 and row < rows and col >=0 and col < cols:
if matrix[row][col] > target:
col -= 1
elif matrix[row][col] < target:
row += 1
elif matrix[row][col] == target:
return True
return False
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/64563.html
摘要：代碼如下超時(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...
摘要：題目要求假設(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...
摘要：題目詳情這道題目要求我們對(duì)一個(gè)正方形矩陣進(jìn)行順時(shí)針度的翻轉(zhuǎn)。并且要求不聲明額外的空間，不能新建二維數(shù)組。輸入數(shù)組旋轉(zhuǎn)后的輸入數(shù)組想法這道題因?yàn)橐笤谖?。所以我們需要找到一種解法，使得每次操作都是交換兩個(gè)元素的位置，最后實(shí)現(xiàn)整個(gè)矩陣的旋轉(zhuǎn)。 題目詳情 You are given an n x n 2D matrix representing an image.Rotate the ima...
摘要：思路一暴力循環(huán)如果我們將矩陣中的每個(gè)子矩陣都枚舉出來(lái)，并計(jì)算其元素和，從而得出小于的最大值即可。 題目要求 Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k. E...
摘要：復(fù)雜度時(shí)間空間為長(zhǎng)度，為大小空間復(fù)雜度是是因?yàn)槲矣么嫘畔ⅲ粍?dòng)態(tài)地存當(dāng)前的路徑如果用來(lái)存信息的話空間復(fù)雜度就是時(shí)間復(fù)雜度對(duì)每個(gè)點(diǎn)都要作為起始點(diǎn)，對(duì)于每個(gè)起始點(diǎn)，拓展一次有四個(gè)可能性四個(gè)鄰居，要拓展次長(zhǎng)度為。思路暴力搜索帶走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...
閱讀 3528·2021-09-22 15:50
閱讀 3233·2019-08-30 15:54
閱讀 2748·2019-08-30 14:12
閱讀 3058·2019-08-30 11:22
閱讀 2079·2019-08-29 11:16
閱讀 3574·2019-08-26 13:43
閱讀 1192·2019-08-23 18:33
閱讀 920·2019-08-23 18:32
