首页 > 代码库 > Search a 2D Matrix
Search a 2D Matrix
你能用最快的速度找到矩阵中是否有我们想要的值吗。例如：
1 2 3
4 5 6
7 8 9
target = 9，return true，target=10，return false。ps：矩阵升序（左到右，上到下），但不一定是连续数字。
解法：
两次二分。
1. 一次二分找到给定的target可能在第几行
2. 第二次二分在那行找到是否有给定的target
class Solution {public: bool searchMatrix(vector<vector<int> > &matrix, int target) { int row = matrix.size(); if (row == 0) return false; int col = matrix[0].size(); int left = 0, right = row - 1; while(left <= right) // 第一次二分找到在right行 { if (matrix[left][0] == target || matrix[right][0] == target) return true; else if (matrix[left][0] < target) left += 1; else if (matrix[right][0] > target) right -= 1; } if (right < 0) return false; // 这个判断不能少，否则会run time error 因为right可能是-1 int l = 0, r = col - 1; while(l <= r) // 第二次在第right行中二分找知否有值 { if (matrix[right][l] == target || matrix[right][r] == target) return true; else if (matrix[right][l] < target) l += 1; else if (matrix[right][r] > target) r -= 1; } return false; }};
Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。