当前位置: 首页> 汽车> 报价 > 手机开发网站怎么做_近期的国际新闻重大事件_百度一下 你就知道官方_上海高端seo公司

手机开发网站怎么做_近期的国际新闻重大事件_百度一下 你就知道官方_上海高端seo公司

时间:2025/7/11 22:56:33来源:https://blog.csdn.net/weixin_53009877/article/details/145768651 浏览次数: 0次
手机开发网站怎么做_近期的国际新闻重大事件_百度一下 你就知道官方_上海高端seo公司

题目来源;

74. 搜索二维矩阵 - 力扣(LeetCode)

题目内容:

给你一个满足下述两条属性的 m x n 整数矩阵:

  • 每行中的整数从左到右按非严格递增顺序排列。

  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false

示例 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

思路分析:

思路一:暴力解法  遍历矩阵(二维数组)

思路二:二分查找

代码实现(思路一:暴力解法):(替大家试过了提交之后会通过)

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n=matrix.size();//行数int m=matrix[0].size();//列数for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==target)return true;}}return false;}
};

代码实现(思路二:二分查找):

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {//二分法  开区间写法int m=matrix.size();int n=matrix[0].size();int left=-1;int right= m*n;while(left+1<right){int mid=left+(right-left)/2;int x=matrix[mid/n][mid%n];if(x==target)  return true;else if(x<target) left=mid;else right=mid;}return false;}
};

题目心得:

  1. 自己写的算法  超时
  2. 思考  用闭区间的二分法  怎么实现
  3. 这个二分法  光顾着背模板了  没有去理解代码  这道题写不出来了 也看不懂题解
  4. 这道题目用开区间去做,在积累一下开区间的代码模板  来源:34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)
    class Solution {// lower_bound 返回最小的满足 nums[i] >= target 的下标 i// 如果数组为空,或者所有数都 < target,则返回 nums.size()// 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]int lower_bound(vector<int>& nums, int target) {int left = -1, right = nums.size(); // 开区间 (left, right)while (left + 1 < right) { // 区间不为空// 循环不变量:// nums[left] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid; // 范围缩小到 (left, mid)} else {left = mid; // 范围缩小到 (mid, right)}}// 循环结束后 left+1 = right// 此时 nums[left] < target 而 nums[right] >= target// 所以 right 就是第一个 >= target 的元素下标return right;}
    
  5. 二分查找原理很容易弄懂,但是在写的时候有边界值问题要处理,我今日遇到的问题就是,答案给出的开区间的写法,我只会闭区间的模板,但我又无法用闭区间去解决这道题。
  6. 对于二分查找还要知道自己要返回什么
  7. (先这样  后面有了全新的理解之后,再回来补充)
关键字:手机开发网站怎么做_近期的国际新闻重大事件_百度一下 你就知道官方_上海高端seo公司

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: