本文主要是介绍【矩阵】240. 搜索二维矩阵 II【中等】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
搜索二维矩阵 II
- 编写一个高效的算法来搜索 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
解题思路
- 1、根据矩阵的特性,可以发现右上角的元素具有一个特性:它是该行最大的元素,并且是该列最小的元素。
- 2、我们可以从右上角开始搜索,如果当前元素等于目标值,则返回 true。
- 3、如果当前元素大于目标值,则目标值必定在当前元素的左侧列,因此向左移动一列。
- 4、如果当前元素小于目标值,则目标值必定在当前元素的下方行,因此向下移动一行。
- 5、重复步骤 3 和 4,直到找到目标值或者越界。
Java实现
public class Search2DMatrixII {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}int m = matrix.length;int n = matrix[0].length;int row = 0, col = n - 1; // Start from the top-right corner从右上角开始
// {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}while (row < m && col >= 0) {if (matrix[row][col] == target) {return true; // Found the target} else if (matrix[row][col] > target) {col--; // Move left in the current row 在当前行向左移动} else {row++; // Move down to the next row 向下移动到下一行}}return false; // Target not found}public static void main(String[] args) {Search2DMatrixII search = new Search2DMatrixII();int[][] 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}};int target1 = 5;int target2 = 20;System.out.println("Target 5 found: " + search.searchMatrix(matrix, target1));System.out.println("Target 20 found: " + search.searchMatrix(matrix, target2));}
}
时间空间复杂度
- 时间复杂度:O(m + n),其中 m 和 n 分别是矩阵的行数和列数
- 空间复杂度:O(1),只需要使用常数级别的额外空间
这篇关于【矩阵】240. 搜索二维矩阵 II【中等】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!