在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]]
给定 target = 7,返回 true。
给定 target = 3,返回 false。
数据范围:矩阵的长宽满足 0 le n,m le 5000≤n,m≤500 , 矩阵中的值满足 0≤val≤109
进阶:空间复杂度 O(1)O(1) ,时间复杂度 O(n+m)O(n+m)
思路:首先看每一行的第一个元素和最后一个元素,看target是否在这个区间
如果在这一个区间,一个一个的比较
如果不在这个区间,直接去看下一个区间
class Solution { public: bool Find(int target, vector> array) { int r, c; r = array.size();//行数 c = array[0].size(); //列数 if(r==0 || c==0) return false; for(int i=0;i =target){ for(int j=0;j 题目答案:(二分法) 1)我么设初始值为右上角元素,arr[0][5] = val,目标tar = arr[3][1]
2)接下来进行二分 *** 作:
3)如果val == target,直接返回
4)如果 tar > val, 说明target在更大的位置,val左边的元素显然都是 < val,间接 < tar,说明第 0 行都是无效的,所以val下移到arr[1][5]
5)如果 tar < val, 说明target在更小的位置,val下边的元素显然都是 > val,间接 > tar,说明第 5 列都是无效的,所以val左移到arr[0][4]
6)继续步骤2)class Solution { public: bool Find(int target, vector> array) { int r,c; r = array.size();//行数 c = array[0].size();//列数 if(r==0 || c==0) return false; int m=0,n=c-1;//行,列 while(m =0){ if(array[m][n]==target) return true; else if(array[m][n] 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)