题目描述
给你一个满足下述两条属性的 m x n
整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target
,如果 target
在矩阵中,返回 true
;否则,返回 false
。
样例输入
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出:true
示例 2:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出:false
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
题解
解1
- 对于每一行,先判断target是否在该行中
- 如果在改行中,则使用二分进行寻找
class Solution {
bool searchTarget(vector<int>& nums,int& target)
{
int left=0,right=nums.size()-1;
while(left<=right)
{
int mid=left+((right-left)>>1);
if(target==nums[mid]) return true;
if(target<nums[mid]) right=mid-1;
if(target>nums[mid]) left=mid+1;
}
return false;
}
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for(vector<int>&nums: matrix)
{
if(target==nums[0] || target==nums[nums.size()-1]) return true;
if(nums[0]<target && target<nums[nums.size()-1])
return searchTarget(nums,target);
}
return false;
}
};
解2
- 直接将二维数组看做一个一维数组,找到中间值:l=0;r=m*n-1;mid=(l+r)/2
- 计算这个“一维数组”中的中间值在二维数组中的位置
- 其中行=mid/n
- 列=mid%n
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m=matrix.size();
if(!m) return false;
int n=matrix[0].size();
int left=0,right=m*n-1;
while(left<=right)
{
int mid=left+((right-left)>>1);
int privlot=matrix[mid/n][mid%n];
if(privlot==target) return true;
if(target<privlot) right=mid-1;
if(target>privlot) left=mid+1;
}
return false;
}
};