河北手机网站制作企业,能够做冶金工程毕业设计的网站,crm客户端,网站建设规划设计报告【问题描述】
在一个二维数组中#xff08;每个一维数组的长度相同#xff09;#xff0c;每一行都按照从左到右递增的顺序排序#xff0c;每一列都按照从上到下递增的顺序排序。请完成一个函数#xff0c;输入这样的一个二维数组和一个整数#xff0c;判断数组中是否含…【问题描述】
在一个二维数组中每个一维数组的长度相同每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。
【坑】
1. 不能以某一行最后一个或者第二行第一个比较大小进行筛选
2. 从左上开始移动容易越界 不能保证两个方向一增一减
1 5 9 10 15 16
【解答思路】
1. 遍历
每一行看成有序递增的数组利用二分查找通过遍历每一行得到答案 时间复杂度是nlogn
public class Solution {public boolean Find(int target, int [][] array) {for(int i0;iarray.length;i){int low0;int higharray[i].length-1;while(lowhigh){int mid(lowhigh)/2;if(targetarray[i][mid])lowmid1;else if(targetarray[i][mid])highmid-1;elsereturn true;}}return false;}
}2.递增 选取右上角或者左下角的元素a[row][col]与target进行比较 当target小于元素a[row][col]时那么target必定在元素a所在行的左边,即col– 当target大于元素a[row][col]时那么target必定在元素a所在列的下边,即row
public class Solution {public boolean Find(int [][] array,int target) {int row0;int colarray[0].length-1;while(rowarray.length-1col0){if(targetarray[row][col])return true;else if(targetarray[row][col])row;elsecol--;}return false;}
}
