LeetCode-240. Search a 2D Matrix II

LeetCode-240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following 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]]

Given target = ​​5​​​, return ​​true​​.

Given target = ​​20​​​, return ​​false​​.

题解：

因为是递增的，所以下一行的同列往右所有元素必大于本行，通过两个指针缩小搜索域即可。

class Solution {public: bool searchMatrix(vector>& matrix, int target) { int n = matrix.size(); if (n == 0) { return false; } int m = matrix[0].size(); if (m == 0) { return false; } int col = 0, row = matrix[0].size() - 1; while (col < n && row >= 0) { if (matrix[col][row] == target) { return true; } else if (matrix[col][row] > target) { row--; } else { col++; } } return false; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。