企业二级网站怎么做,纯流量卡免费申请入口,办网站 哪些许可,建e网官网效果图一、问题描述#xff1a; 给你一个满足下述两条属性的 m x n 整数矩阵#xff1a; 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target #xff0c;如果 target 在矩阵中#xff0c;返回 true #xff1b;否则 给你一个满足下述两条属性的 m x n 整数矩阵 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。 二、二分查找
1、思路分析使用二分查找的思想将二维矩阵当作一维数组来处理。
将二维矩阵展开成一维数组后可以通过计算元素在一维数组中的索引来访问对应的元素。 设定搜索范围为一维数组的起始位置到结束位置然后在该范围内进行二分查找。 在每次迭代中计算中间元素的值并与目标值进行比较根据比较结果更新搜索范围。
2、代码示例
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int n matrix.length, m matrix[0].length; // 获取矩阵的行数和列数int low 0, high m * n - 1; // 初始化二分查找的搜索范围为一维数组的起始位置到结束位置while (low high) { // 当搜索范围有效时执行循环int mid low (high - low) / 2; // 计算中间元素的索引int x matrix[mid / m][mid % m]; // 获取中间元素的值if (x target) // 如果中间元素大于目标值high mid - 1; // 更新搜索范围为左半部分else if (x target) // 如果中间元素小于目标值low mid 1; // 更新搜索范围为右半部分else // 如果中间元素等于目标值return true; // 返回true}return false; // 若搜索范围无效则返回false}
}3、 时间复杂度分析
设矩阵的行数为n列数为m。在初始化后二分查找的时间复杂度为O(log(nm))。 每次迭代中都是在一维数组中进行操作因此单次迭代的时间复杂度为O(1)。 整体的时间复杂度取决于二分查找的次数即O(log(nm))。
三、搜索二叉树法思想类似
1、思路分析
在二叉搜索树中每个节点都有左子树和右子树且左子树中的所有节点的值都小于当前节点的值右子树中的所有节点的值都大于当前节点的值。因此可以利用这个性质在BST中进行高效的搜索。这种思路称为二分搜索每次搜索都可以将搜索范围缩小一半因此搜索效率很高。虽然二维矩阵不是二叉搜索树但可以利用类似的思想在每一步中根据当前元素与目标值的大小关系决定搜索范围的缩小方向。
2、具体步骤
从二维矩阵的右上角开始利用矩阵的性质进行搜索 ①如果当前元素大于目标值则目标值不可能在当前元素的列中因此将列索引向左移动。 ②如果当前元素小于目标值则目标值不可能在当前元素的行中因此将行索引向下移动。 ③如果当前元素等于目标值则找到目标值返回true。 重复以上步骤直到找到目标值或者搜索范围超出矩阵边界。
3、代码示例
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int n 0, m matrix[0].length - 1;while(n matrix.length m 0){if(matrix[n][m] target) m--;else if(matrix[n][m] target) n;else return true;}return false;}
}4、 时间复杂度分析
设矩阵的行数为n列数为m。在最坏情况下搜索范围会在矩阵的对角线上移动因此时间复杂度为O(n m)。 在每次迭代中都是在矩阵中进行操作因此单次迭代的时间复杂度为O(1)。 整体的时间复杂度为O(n m)。
