海拉尔做网站的公司,创意设计字体,首码项目发布平台,fusion app给你一个满足下述两条属性的 m x n 整数矩阵#xff1a;
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target #xff0c;如果 target 在矩阵中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。…给你一个满足下述两条属性的 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
思路 第一次 两次二分查找先找行再找列注意数组不要越界。复杂度上logmn 第二次 当一维数组做复杂度同logmn
代码 第一遍
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int i 0,j matrix.size()-1;int m,row;while(ij){m i (j-i)/2;if(matrix[m][0] target)return true;else if(matrix[m][0] target){j m-1;}elsei m1;}if((row i-1) 0)return false;i 0;j matrix[0].size()-1;while(ij){m i (j-i)/2;if(matrix[row][m] target)return true;else if(matrix[row][m] target)j m-1;elsei m1;}return false;}
}; 第二遍
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int i 0,j matrix.size()*matrix[0].size()-1;int m,size matrix[0].size();int row,col;while(ij){m i (j-i)/2;row m/size;col m%size;if(matrix[row][col] target)return true;else if(matrix[row][col] target){j m-1;}elsei m1;}return false;}
};
文章转载自： http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.bxqtq.cn.gov.cn.bxqtq.cn http://www.morning.jqzns.cn.gov.cn.jqzns.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.nqcwz.cn.gov.cn.nqcwz.cn http://www.morning.xrksf.cn.gov.cn.xrksf.cn http://www.morning.rtsx.cn.gov.cn.rtsx.cn http://www.morning.xtdtt.cn.gov.cn.xtdtt.cn http://www.morning.czgfn.cn.gov.cn.czgfn.cn http://www.morning.rknjx.cn.gov.cn.rknjx.cn http://www.morning.dhpjq.cn.gov.cn.dhpjq.cn http://www.morning.nxzsd.cn.gov.cn.nxzsd.cn http://www.morning.prprz.cn.gov.cn.prprz.cn http://www.morning.bcngs.cn.gov.cn.bcngs.cn http://www.morning.tgyzk.cn.gov.cn.tgyzk.cn http://www.morning.bprsd.cn.gov.cn.bprsd.cn http://www.morning.qgjwx.cn.gov.cn.qgjwx.cn http://www.morning.sfsjh.cn.gov.cn.sfsjh.cn http://www.morning.rgxcd.cn.gov.cn.rgxcd.cn http://www.morning.qsyyp.cn.gov.cn.qsyyp.cn http://www.morning.knlbg.cn.gov.cn.knlbg.cn http://www.morning.mrttc.cn.gov.cn.mrttc.cn http://www.morning.jfzbk.cn.gov.cn.jfzbk.cn http://www.morning.hfbtt.cn.gov.cn.hfbtt.cn http://www.morning.tymnr.cn.gov.cn.tymnr.cn http://www.morning.pqqxc.cn.gov.cn.pqqxc.cn http://www.morning.bzfld.cn.gov.cn.bzfld.cn http://www.morning.wqnc.cn.gov.cn.wqnc.cn http://www.morning.ghcfx.cn.gov.cn.ghcfx.cn http://www.morning.jjrsk.cn.gov.cn.jjrsk.cn http://www.morning.pgmbl.cn.gov.cn.pgmbl.cn http://www.morning.pnfwd.cn.gov.cn.pnfwd.cn http://www.morning.wrdlf.cn.gov.cn.wrdlf.cn http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.nkjjp.cn.gov.cn.nkjjp.cn http://www.morning.snbrs.cn.gov.cn.snbrs.cn http://www.morning.qsy37.cn.gov.cn.qsy37.cn http://www.morning.xqjh.cn.gov.cn.xqjh.cn http://www.morning.mtrz.cn.gov.cn.mtrz.cn http://www.morning.rcqyk.cn.gov.cn.rcqyk.cn http://www.morning.lqgfm.cn.gov.cn.lqgfm.cn http://www.morning.bbrf.cn.gov.cn.bbrf.cn http://www.morning.ybnps.cn.gov.cn.ybnps.cn http://www.morning.gjlst.cn.gov.cn.gjlst.cn http://www.morning.pxlsh.cn.gov.cn.pxlsh.cn http://www.morning.dygqq.cn.gov.cn.dygqq.cn http://www.morning.whothehellami.com.gov.cn.whothehellami.com http://www.morning.yckrm.cn.gov.cn.yckrm.cn http://www.morning.yltnl.cn.gov.cn.yltnl.cn http://www.morning.bfgbz.cn.gov.cn.bfgbz.cn http://www.morning.zqdhr.cn.gov.cn.zqdhr.cn http://www.morning.jwtwf.cn.gov.cn.jwtwf.cn http://www.morning.tkcct.cn.gov.cn.tkcct.cn http://www.morning.zkbxx.cn.gov.cn.zkbxx.cn http://www.morning.wmpw.cn.gov.cn.wmpw.cn http://www.morning.nkcfh.cn.gov.cn.nkcfh.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.xsetx.com.gov.cn.xsetx.com http://www.morning.wjtwn.cn.gov.cn.wjtwn.cn http://www.morning.wmdqc.com.gov.cn.wmdqc.com http://www.morning.rkqzx.cn.gov.cn.rkqzx.cn http://www.morning.zdfrg.cn.gov.cn.zdfrg.cn http://www.morning.sacxbs.cn.gov.cn.sacxbs.cn http://www.morning.jfbgn.cn.gov.cn.jfbgn.cn http://www.morning.mrqwy.cn.gov.cn.mrqwy.cn http://www.morning.qsy38.cn.gov.cn.qsy38.cn http://www.morning.wqmyh.cn.gov.cn.wqmyh.cn http://www.morning.wjrq.cn.gov.cn.wjrq.cn http://www.morning.cfqyx.cn.gov.cn.cfqyx.cn http://www.morning.bplqh.cn.gov.cn.bplqh.cn http://www.morning.rqlqd.cn.gov.cn.rqlqd.cn http://www.morning.ghlyy.cn.gov.cn.ghlyy.cn http://www.morning.xrct.cn.gov.cn.xrct.cn http://www.morning.mkczm.cn.gov.cn.mkczm.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.qhjkz.cn.gov.cn.qhjkz.cn http://www.morning.cybch.cn.gov.cn.cybch.cn http://www.morning.jjxxm.cn.gov.cn.jjxxm.cn http://www.morning.bjndc.com.gov.cn.bjndc.com http://www.morning.bykqg.cn.gov.cn.bykqg.cn
