题目描述
在一个二维数组中(每个以为数组的长度相同),每一行都按照从左到右递增的顺序排列,每一列都按照从上到下递增的顺序排列。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
思路
根据题意,设一个二维数组如下:
- 如果数组为空,直接返回false
- 获取数组的行数与列数
- 当前值所在的行索引与列索引,初始为第一列、最后一行
- 遍历数组,将目标值与当前值比较
- 如果目标值 > 当前值,说明目标值可能在当前值下方
- 如果目标值 < 当前值,说明目标值可能在当前值左方
- 如果目标值 = 当前值,说明数组中存在该整数
- 如果遍历完整个数组都没找到:目标值 = 当前值,说明数组中不存在该整数
实现
public class Solution { public boolean Find(int target, int [][] array) { // 1 如果数组为空,直接返回false if (array == null) { return false; } // 2 获取数组的行数与列数 int rowLength = array.length; int colLength = array[0].length; // 3 当前值所在的行索引与列索引,初始为第一列、最后一行 int rowIndex = 0; int colIndex = colLength - 1; // 4 遍历数组,将目标值与当前值比较 while(rowIndex < rowLength && colIndex >= 0) { // 4.1 如果目标值 > 当前值,说明目标值可能在当前值下方 if(target > array[rowIndex][colIndex]) { rowIndex++; } else if(target < array[rowIndex][colIndex]) { // 4.2 如果目标值 < 当前值,说明目标值可能在当前值左方 colIndex--; } else { // 4.3 如果目标值 = 当前值,说明数组中存在该整数 return true; } } // 5 如果遍历完整个数组都没找到:目标值 = 当前值,说明数组中不存在该整数 return false; } }