文章目錄
- 題目描述
- 知識點
- 解法一——二分
- 結果
- 碼前思考
- 代碼實作
- 解法二——思維⭐⭐⭐⭐⭐(重要！！！)
- 結果
- 碼前思考
- 代碼實作
- 碼後反思
- 參考文檔
- 二刷代碼
題目描述
矩陣的每行從左到右是升序，每列從上到下也是升序，在矩陣中查找某個數。
知識點
二分、分支、思維
解法一——二分
結果
碼前思考
看到有序，第一反應就是二分查找。最直接的做法，一行一行的進行二分查找即可。
此外，結合有序的性質，一些情況可以提前結束：
- 比如某一行的第一個元素大于了 target ，目前行和後邊的所有行都不用考慮了，直接傳回 false。
- 某一行的最後一個元素小于了 target ，目前行就不用考慮了，換下一行。
時間複雜度的話，如果是
m
行
n
列，就是 O ( m l o g ( n ) ) O(mlog(n)) O(mlog(n))。
代碼實作
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0){
return false;
}
for(int i=0;i<matrix.length;i++){
if(matrix[i][0] > target){
break;
}
if(matrix[i][matrix[i].length-1] < target){
continue;
}
int col = binarySearch(matrix[i],target);
if(col != -1){
return true;
}
}
return false;
}
private int binarySearch(int[] nums,int target){
int start = 0;
int end = nums.length -1;
while(start <= end){
int mid = (start+end) >>> 1;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
start = mid+1;
}else{
end = mid-1;
}
}
return -1;
}
}
解法二——思維⭐⭐⭐⭐⭐(重要！！！)
結果
碼前思考
需要很敏銳的觀察力了。
數組從左到右和從上到下都是升序的，如果從右上角出發開始周遊呢？
會發現每次都是向左數字會變小，向下數字會變大，有點和二分查找樹相似。二分查找樹的話，是向左數字變小，向右數字變大。
是以我們可以把
target
和目前值比較。
- 如果
target
- 如果
target
- 如果相等的話，直接傳回
true
也可以換個角度思考。
如果
target
的值小于目前值，也就意味着目前值所在的列肯定不會存在
target
了，可以把目前列去掉，從新的右上角的值開始周遊。
同理，如果
target
的值大于目前值，也就意味着目前值所在的行肯定不會存在
target
了，可以把目前行去掉，從新的右上角的值開始周遊。
看下邊的例子。
[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 = 9，如果我們從 15 開始周遊, cur = 15
target < 15, 去掉目前列, cur = 11
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26]
target < 11, 去掉目前列, cur = 7
[1, 4, 7],
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
target > 7, 去掉目前行, cur = 8
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
target > 8, 去掉目前行, cur = 9, 周遊結束
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
不管從哪種角度考慮，代碼的話都是一樣的。
時間複雜度就是每個節點最多周遊一遍了， O ( m + n ) O(m + n) O(m+n)。
代碼實作
//從右上角開始周遊，類似于BST樹來操作
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0 || matrix[0].size() == 0){
return false;
}
int row = 0;
int col = matrix[0].size()-1;
while(row < matrix.size() && col >= 0){
if(matrix[row][col] > target){
col--;
}else if(matrix[row][col] < target){
row++;
}else{
return true;
}
}
return false;
}
};
碼後反思
- 之前用的暴力方法，暴力會逾時。。。時間複雜度為 O ( m ∗ n ) O(m*n) O(m∗n) ，非常不可以！！！即使我采用了各種剪枝，但是仍然在最壞的情況下會逾時。這就是從 左上角 和 右上角 開始的差別。
//采用DFS并且搭配上一定的剪枝操作 class Solution { public: vector<vector<bool> > vis; bool flag = false; //用于标記是否找到 int dir[2][2] = {{1,0},{0,1}}; int m,n; bool searchMatrix(vector<vector<int>>& matrix, int target) { m = matrix.size(); if(m == 0){ return false; } n = matrix[0].size(); if(n == 0){ return false; } vis.assign(m,vector<bool>(n,false)); search(matrix,target,0,0); return flag; } void search(vector<vector<int>>& matrix, int target,int x,int y){ //printf("x:%d y:%d\n",x,y); if(!flag){ vis[x][y] = true; if(matrix[x][y] == target){ flag = true; return; }else{ for(int i=0;i<2;i++){ int newX = x + dir[i][0]; int newY = y + dir[i][1]; if(newX >=m || newY >= n || vis[newX][newY] || flag){//被通路過了 continue; }else{ //代表可以通路 search(matrix,target,newX,newY); } } } return; } } };
參考文檔
- 詳細通俗的思路分析，多解法
二刷代碼
//采用類似于二叉樹的寫法進行解題
class Solution {
public:
int dir[2][2] = {{0,-1},{1,0}};
bool searchMatrix(vector<vector<int>>& matrix, int target) {
bool isFind = false;
int m = matrix.size();
if(m==0){
return false;
}
int n = matrix[0].size();
int x=0;
int y=n-1;
//遇到邊界就會挂掉
while(isFind != true && x<m && y>=0){
if(matrix[x][y] == target){
isFind=true;
}else{
if(target<matrix[x][y]){
x += dir[0][0];
y += dir[0][1];
}else{
x += dir[1][0];
y += dir[1][1];
}
}
}
return isFind;
}
};