LeetCode 74

2024-07-12 08:06| 来源: 网络整理| 查看: 265

一、题目介绍

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

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

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true 示例 2:

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

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

二、解题思路

由题可知，每一行的元素从左到右依次增大，且每一行的第一个元素大于前一行的最后一个元素。因此我们可以总结出来：

（1）同一行中，右边的元素大于左边的元素。

（2）同一列中，下边的元素大于上边的元素。

利用以上两个特性，我们从二维矩阵的左下角出发，如果当前元素大于target，则需要到上一行去查找目标值；如果当前元素小于目标值，则需要到下一列去查找target；如果当前元素等于target，则可以直接返回true；如果直到遍历到右上角仍未找到target，则返回false。（同理也可以右上角----->左下角）

三、解题代码 class Solution { public: bool searchMatrix(vector& matrix, int target) { int m = matrix.size(); if(m == 0) return false; int n = matrix[0].size(); if(n == 0) return false; int r = m - 1; int c = 0; while(r >= 0 && c < n) { if(matrix[r][c] == target) return true; else if(matrix[r][c] > target) r--; else c++; } return false; } }; 四、解题结果

【本文地址】

公司简介

联系我们