《剑指offer》之二维数组中的查找
前言
在家呆着没什么事做，今天开始每天刷一道算法题吧。不多不少，重在自己能坚持下去。所有的算法题都是用Java写的，有兴趣的小伙伴可以一起啊。
题目
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析
这道题目是一个有序的二维数组，给我们一个数判断这个数是否在二维数组中。这里的重点是判断，而不用对二维数组进行校验，所以这里实现起来其实也比较简单。
解法一
我们完全可以暴力解决，遍历这个二维数组，判断是否在其中。
public boolean Find(int target, int [][] array) {
if(array==null|| array.length <= 1){
return false;
}
for(int i=0;i<array.length;i++){
for (int j = 0; j < array[0].length; j++) {
if(array[i][j]==target){
return true;
}
}
}
return false;
}但是这样很明显没有用到二维数组有序的这个条件，也就算不上一道算法题了。
解题二
既然上面说了，我们就充分利用有序才行。我们中二维数组应该是类似下列的形式
1 2 3 4 2 3 4 6 4 5 7 8
如果目标数小于每行的最后一个数，则目标数可能在这一行，从这一行往前找，如果发现某一个值小于目标值，就从下一行最后一个值开始找。比如上面的例子，需要找5 的话 1、先5和第一行的最后一个值4比较，大于4。i++ 2、5和第二行的6比较，小于6 。j-- 3、5和第二行的4 比较，大于4。i++ 4、5 和第三行的8比较，小于8 。j-- 5、5 和第三行的7比较，小于7 。j-- 6、5 和第三行的5比较，等于5 。返回true
所以代码如下：
public static boolean find(int [][] array,int target) {
int i=0;
int j=array[0].length-1;
int n=array.length;
while(i<n && j>=0){
if(target==array[i][j])
return true;
else if(target>array[i][j])
i++;
else
j--;
}
return false;
}源代码
package com.quellanan.algorithm.day1;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入行数");
int n=scanner.nextInt();
System.out.println("请输入列数");
int m=scanner.nextInt();
System.out.println("请输入二维数组");
int[][] array=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
array[i][j]=scanner.nextInt();
System.out.print(array[i][j]+"\t");
}
System.out.println("");
}
System.out.println("请输入目标数字");
int targer=scanner.nextInt();
System.out.println(find(array,targer));
}
public static boolean find(int [][] array,int target) {
int i=0;
int j=array[0].length-1;
int n=array.length;
while(i<n && j>=0){
if(target==array[i][j])
return true;
else if(target>array[i][j])
i++;
else
j--;
}
return false;
}
}运行结果
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-02-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录