Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For 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 =
, return
- 5
.
- true
Given target =
, return
- 20
.
- false
解题思路:每次选右上角的元素拿来比较,如果大于target,左移一列,如果小于target则下移一行。
- class Solution {
- public: bool searchMatrix(vector < vector < int >> &matrix, int target) {
- if (matrix.empty()) return false;
- int n = matrix.size(),
- m = matrix[0].size();
- int row = 0,
- col = m - 1;
- while (row < n && col >= 0) {
- if (matrix[row][col] > target) {
- col--;
- } else if (matrix[row][col] < target) {
- row++;
- } else return true;
- }
- return false;
- }
- };
来源: http://www.bubuko.com/infodetail-2339772.html