剑指Offer算法题 01.二维数组的查找
01.在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
实现思路:
从右上角开始取数字来与待查找值来比较;
如果右上角的数字 > 待查找值,那么该列可以剔除;(每一列从上到下递增,右上角的数字是所在列最小的,因此可以剔除该列);
如果右上角的数字 < 待查找值,那么该行可以剔除;(每一行从左到有递增,右上角的数字是所在行最大的,因此可以剔除该行);
直到找到要查找的数字,或者查找范围为空。
实现代码:
public class Solution { public boolean Find(int target, int [][] array) { if (array == null || array.length < 1 || array[0].length < 1){ return false; } int rows = array.length; // 数组行数 int cols = array[0].length; // 数组的列数 int row = 0; // 起始的行号 int col = cols - 1; // 起始的列号 //要查找的位置确保在数组之内 while (row < rows && col >= 0){ if (array[row][col] == target){ return true; }else if (array[row][col] > target){ col -- ; // 如果当前数(右上角) > 目标数字 则查找目标在当前数的左边 列号 -1 }else { row ++; // 如果当前数(右上角) < 目标数字 则查找目标在当前数的下方,行号 +1 } } return false; } }