IT评测·应用市场-qidao123.com

标题: 力扣hot100 ——搜刮二维矩阵 || m+n复杂度优化解法 [打印本页]
作者: 大连全瓷种植牙齿制作中心    时间: 2025-2-21 07:01
标题: 力扣hot100 ——搜刮二维矩阵 || m+n复杂度优化解法
编写一个高效的算法来搜刮 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

解题思路：
借助行和列有序特性，不断按行或者列缩小范围；途中数字表现每次执行，不同颜色框出的范围就是每次缩小后的区域，由于不是按行就是按列缩小，以是时间复杂度就是O（m+n）

  1. class Solution {
  2. public:
  3.     bool searchMatrix(vector<vector<int>>& matrix, int target) {
  4.         // 边界缩小查找
  5.         // 从右上角开始缩小；先水平调整，然后竖直缩小
  6.         // 借助行和列有序特性，不断按行或者列缩小范围；由于不是按行就是按列缩小，所以时间复杂度就是O（m+n）
  7.         int rows = matrix.size(),clos = matrix[0].size(); // row 行上限  clo 列上限
  8.         int row = 0,clo = clos - 1;
  9.         if(target > matrix[rows-1][clos - 1]){
  10.             return false;
  11.         }
  12.         while(row < rows && clo >= 0){
  13.             if(matrix[row][clo] == target){
  14.                 return true;
  15.             }
  16.             else if(matrix[row][clo] > target){
  17.                 --clo;
  18.             }
  19.             else{
  20.                 ++row;
  21.             }
  22.         }
  23.         return false;
  25.     }
  26. };
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4