目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
撰寫一個高效的演算法來搜索 m x n 矩陣 matrix 中的一個目標值 target ，該矩陣具有以下特性：
- 每行的元素從左到右升序排列，
- 每列的元素從上到下升序排列，
示例 1：
輸入：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]], target = 5
輸出：true
示例 2：
輸入：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]], target = 20
輸出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matix[i][j] <= 109- 每行的所有元素從左到右升序排列
- 每列的所有元素從上到下升序排列
-109 <= target <= 10^9
2、思路
(單調性掃描) O ( n + m ) O(n+m) O(n+m)
在m x n矩陣 matrix中我們可以發現一個性質：對于每個子矩陣右上角的數x，x左邊的數都小于等于x，x下邊的數都大于x，
因此我們可以從整個矩陣的右上角開始列舉，假設當前列舉的數是 x：
- 如果
x等于target，則說明我們找到了目標值，回傳true； - 如果
x小于target，則x左邊的數一定都小于target，我們可以直接排除當前一整行的數； - 如果
x大于target，則x下邊的數一定都大于target，我們可以直接排序當前一整列的數；
排除一整行就是讓列舉的點的橫坐標加一，排除一整列就是讓縱坐標減一，當我們排除完整個矩陣后仍沒有找到目標值時，就說明目標值不存在，回傳false，
具體程序如下：
- 1、初始化
i = 0,j = matrix[0].size() - 1， - 2、如果
matrix[i][j] == target，回傳true， - 3、如果
matrix[i][j] < target，i++，排除一行， - 4、如果
matrix[i][j] > target，j--，排除一列， - 5、如果出界還未找到
target，則回傳false，
時間復雜度分析： 每一步會排除一行或者一列，矩陣一共有 n n n 行， m m m 列，所以最多會進行 n + m n+m n+m步，所以時間復雜度是 O ( n + m ) O(n+m) O(n+m)，
3、c++代碼
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(!matrix.size() && !matrix[0].size()) return false;
int i = 0, j = matrix[0].size() - 1; //矩陣右上角
while(i < matrix.size() && j >= 0)
{
if(matrix[i][j] == target) return true;
else if( matrix[i][j] < target) i++; //排除一行
else if( matrix[i][j] > target) j--; //排除一列
}
return false;
}
};
4、java代碼
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 && matrix[0].length == 0) return false;
int i = 0, j = matrix[0].length - 1; //矩陣右上角
while(i < matrix.length && j >= 0)
{
if(matrix[i][j] == target) return true;
else if( matrix[i][j] < target) i++; //排除一行
else if( matrix[i][j] > target) j--; //排除一列
}
return false;
}
}
原題鏈接： 240. 搜索二維矩陣 II
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/295161.html
標籤：java
上一篇：# Day14-Java基礎