《剑指Offer》第1题(Java实现):在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

时间:2023-03-08 15:25:45
《剑指Offer》第1题(Java实现):在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

一、题目描述

  在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
二、思路解析
  此问题使用类似于二分查找的算法。右上角元素(第一行最后一列)的元素是第一个元素与第二行元素构成的递增排序的分割点,因为此元素的左面元素都比此元素小,此元素的下面元素都比此元素大(类似于二分查找中的中点处的元素)。所以每次循环,比较目标元素target与右上角元素的大小关系,如果相等,则找到,返会true即可。如果target元素大于右上角元素,则target大于第一行所有元素,所以target不能出现在第一行,所以把第一行清除。如果target元素小于右上角元素,则target小于最后一列所有元素,不可能出现在最优一列,所以可以把最后一列清除。清除第一行或者第一列之后,继续采用上述方式,用右上角元素与target元素进行比较。如果当列数较小到零或者行数增加到最后一行都没有找到target,则返回false,说明此二维数组中没有与target相同的元素
三、Java代码
  

public class Solution {
public boolean Find(int target, int [][] array) {
int rows = array.length;//获得初始行数
int cols = array[0].length;//获得初始的列数

boolean flag = false;//设置标志位为false
int row = 0;//动态行数默认从0开始
int col = cols-1;//动态列数默认从最后一列开始

while(row<=rows-1 && col>=0){//当没有达到最后一行并且没有达到第一列的时候
if(array[row][col] == target){//如果对象元素等于target,找到,break
flag = true;
break;
}else if(array[row][col] < target){
row++;
}else{
col--;
}
}
return flag;
}
}

以上均为个人理解,如果不正确、不合理或者可以优化的地方,欢迎下方留言。