如题 (总结)
-认真读题, 还WA了一次,
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
这题也没有说数据量,暂且二分吧.
借鉴学习文章列表
链接1:
链接2:
ALiBaBaJavaCodingGuideLines
1.问题
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
2. 代码
/**
*在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
* 每一列都按照从上到下递增的顺序排序。
* 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
* 比如3*3的矩阵:
* 1 2 3
* 2 3 4
* 3 4 55
* @author szs
*/
public class Solution {
public boolean Find(int target, int [][] array) {
int width = array[0].length;
int height = array.length;
// int line = binaryIncludeFind(array,0,height-1,target,width);
int line;
for( line=0; line<= height-1;line++){
boolean ans= binaryEqualFind(array[line],0 , width-1 ,target );
if(ans)return true;
}
return false;
}
/**
* @description 二分查找某个值是否在某行,饭后是/否
* @author SongZeShan
* @date 2019/7/10 16:38
* @param
* @return
*/
private boolean binaryEqualFind(int[] array,int low,int high,int val){
if(low>high){
return false;
}
if(val<array[low] || val>array[high]){
return false;
}else{
int mid = (low+high)/2;
if(array[low]<=val && array[mid]>val){
return binaryEqualFind(array, low, mid-1, val);
}else if(array[mid]==val){
return true;
}else{
return binaryEqualFind(array, mid+1, high, val);
}
}
}
}
3.测试类
/**
* FileName: ${FILENAME}
* 类的详细说明
*
* @author SongZeShan
* @version 1.0
* @Date 2019/7/10 16:33
*/
public class Test {
public static void main(String[] args) {
int arr[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}} ;
Solution solution = new Solution();
for(int i=1;i<=6;i++)
System.out.println(solution.Find(i, arr));
}
}
测试结果
true
true
false
true
false
true
Process finished with exit code 0
