Leetcode刷题74. 搜索二维矩阵_二维数组是s型增长,搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
 

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
 

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

感谢御三五的详细解法【坐标轴法】搜索二维矩阵

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
//		return searchMatrixI(matrix, target);
//		return searchMatrixII(matrix, target);
		return searchMatrixIII(matrix, target);
	}
 
	//方法三：坐标轴法
	//根据题意可知，二维数组从左往右递增，从上往下递增，因此可以得出结论：
	//1.某列的某个数字，该数之下的数字都比其大
	//2.某行的某个数字，该数之左的数字都比其小
	//因此以二维数组的右上角为坐标原点，建立直角坐标轴，若当前数字小于要查找的数，则往下移动一位；若当前数字大于要查找的数，则往左移动一位
	//时间复杂度O(m+n)，空间复杂度O(1)
	private boolean searchMatrixIII(int[][] matrix, int target) {
		int row = 0;
		int column = matrix[0].length - 1;
		while (row < matrix.length && column >= 0) {
			int num = matrix[row][column];
			if (num < target) {
				row++;
			} else if (num > target) {
				column--;
			} else {
				return true;
			}
		}
		return false;
	}
 
	//方法二：二分法
	//将二维矩阵的索引转换为一维矩阵索引，由题意可知在绝对索引上数字递增，因此可以使用二分查找法
	//假设二维矩阵是m行n列，(i,j)的绝对索引idx，求得i=idx / n, j=idx % n
	//时间复杂度O(logmn)，空间复杂度O(1)
	private boolean searchMatrixII(int[][] matrix, int target) {
		int m = matrix.length;
		int n = matrix[0].length;
		int left = 0;
		int right = m * n - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int x = matrix[mid / n][mid % n];
			if (x < target) {
				left = mid + 1;
			} else if (x > target) {
				right = mid - 1;
			} else {
				return true;
			}
		}
		return false;
	}
 
	//方法一：暴力解法
	//时间复杂度O(m*n)，空间复杂度O(1)
	private boolean searchMatrixI(int[][] matrix, int target) {
		if (matrix == null || matrix[0] == null) {
			return false;
		}
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (matrix[i][j] == target) {
					return true;
				}
			}
		}
		return false;
	}
}