原题网址:https://www.lintcode.com/zh-cn/old/problem/search-a-2d-matrix-ii/#
38. 搜索二维矩阵 II
写出一个高效的算法来搜索m×n矩阵中的值,返回这个值出现的次数。
这个矩阵具有以下特性:
- 每行中的整数从左到右是排序的。
- 每一列的整数从上到下是排序的。
- 在每一行或每一列中没有重复的整数。
您在真实的面试中是否遇到过这个题?
Yes
样例
考虑下列矩阵:
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出target = 3,返回 2
挑战
要求O(m+n) 时间复杂度和O(1) 额外空间
标签
非挑战版思路:
脑子驴了,看到排序数组(矩阵)的搜索问题第一时间想到的就是二分查找法……对每行进行二分查找统计个数,时间复杂度O(m×log(n))。
AC代码:
class Solution { public: /** * @param matrix: A list of lists of integers * @param target: An integer you want to search in matrix * @return: An integer indicate the total occurrence of target in the given matrix */ int searchMatrix(vector<vector<int>> &matrix, int target) { // write your code here if (matrix.empty()) { return 0; } int result=0; int rowSize=matrix.size(); int colSize=matrix[0].size(); if (target<matrix[0][0]||target>matrix[rowSize-1][colSize-1]) { return result; } for (int i=0;i<rowSize;i++) { int begin=0,end=colSize-1,mid=begin+end/2; while(begin<=end) { if (target==matrix[i][mid]) { ++result; break; } else if (target<matrix[i][mid]) { end=mid-1; mid=(begin+end)/2; } else { begin=mid+1; mid=(begin+end)/2; } } } return result; } };
挑战版 参考:
https://www.cnblogs.com/edisonchou/p/4737944.html 可以多看几遍
https://blog.csdn.net/ljlstart/article/details/48517509
利用给定矩阵的特点,可以从右上角走到左下角,也可以从左下角走到右上角。这样每次移动时要么剔除当前行要么剔除当前列。
第一种,若当前点大于target,当前列-1,即判断matrix【row】【col-1】;
若当前点小于target,当前行+1,即判断matrix【row+1】【col】;
若当前点等于target,计数器加1,然后当前行+1,当前列-1;
重复以上步骤直到左下角。
AC代码:
class Solution { public: /** * @param matrix: A list of lists of integers * @param target: An integer you want to search in matrix * @return: An integer indicate the total occurrence of target in the given matrix */ int searchMatrix(vector<vector<int>> &matrix, int target) { // write your code here if (matrix.empty()) { return 0; } int result=0; int rowSize=matrix.size(); int colSize=matrix[0].size(); if (target<matrix[0][0]||target>matrix[rowSize-1][colSize-1]) { return result; } int i=0,j=colSize-1; while(i>=0&&i<rowSize&&j>=0&&j<colSize) { if (matrix[i][j]==target) { ++result; ++i; --j; } else if (matrix[i][j]<target) { ++i; } else { --j; } } return result; } };