"剑指Offer:二维数组中的查找(Java代码)"

需积分: 1 0 下载量 172 浏览量 更新于2024-01-18 收藏 870KB PDF 举报
题目要求编写一个函数,判断一个二维数组中是否包含某个整数。给定的二维数组是有序的,每一行从左到右递增,每一列从上到下递增。函数需要输出一个布尔值,true表示找到了目标整数,false表示没有找到。 首先我们可以观察到,从右上角开始查找是一个不错的策略。因为右上角的数是当前行的最大值,同时也是当前列的最小值。根据二维数组的有序性质,我们可以根据目标整数与右上角的数的大小比较,来决定下一步搜索的方向。 具体的算法可以如下: 1. 如果二维数组的行数或列数为0,那么直接返回false。 2. 初始化两个指针i和j,分别指向二维数组的右上角。 3. 进入一个循环,循环的条件是i小于二维数组的行数且j大于等于0: a. 如果目标整数与二维数组的右上角数相等,那么直接返回true,表示找到了目标整数。 b. 如果目标整数小于二维数组的右上角数,那么目标整数必然在当前数的左边列,所以j减小1。 c. 如果目标整数大于二维数组的右上角数,那么目标整数必然在当前数的下边行,所以i增加1。 4. 如果循环结束,还没有找到目标整数,那么返回false,表示未找到。 下面是使用Java语言实现的代码: ``` class Solution { public boolean find(int[][] array, int target) { int row = array.length; if (row == 0) { return false; } int col = array[0].length; if (col == 0) { return false; } int i = 0, j = col - 1; // 从右上角开始 while (i < row && j >= 0) { if (target == array[i][j]) { return true; } else if (target < array[i][j]) { j--; } else { i++; } } return false; // 未找到目标整数 } } ``` 这样,我们就实现了一个函数,可以判断一个二维数组中是否包含某个整数。我们通过从右上角开始查找,不断根据比较结果调整搜索方向,可以在时间复杂度为O(m+n)的情况下找到目标整数。其中m为二维数组的行数,n为二维数组的列数。 建议大家可以尝试在输入描述给定的二维数组和目标整数上进行调试,验证代码的正确性。