[剑指offer Java实现]4.二维数组中是否存在一个给定的值

xiaoxiao2021-02-28  11

题目

在一个二维数组中,每一行的值都是按照从左到右递增的顺序排列,每一列都是按照从上到下递增的顺序排列 请设计一个方法,输入这样的一个二维数组和一个数字,判断这个数字是否存在于这个数组中

解决方法

方法一

遍历整个二维数组进行查找

当然,面试中只写出方法一的解法,面试官一定不会满意,所以我们得谋求另一种思路

方法二

假设有如下二维数组,我们在这个二维数组中查找是否存在 7

我们可以定义一个点,从右上角开始,循环判断该点的值与给定点值之间的关系, 如果该点的值小于给定的值,该点坐标下移一行, 小于给定点的值,坐标左移一行, 相等,返回true,循环判断直到该点的坐标越界 给定点的值为 9, 9 > 7,下一次只需要在 9 的右边查找 8 > 7,下一次在 8 的左边查找 2 < 7,下一次在 2 的下边查找 4 < 7,下一次在 4 的下边查找 7 == 7,查找成功,返回 true

方法实现

package Test; /* * 题目:二维数组查找 * 在一个二维数组中,每一行的值都是按照从左到右递增的顺序排列,每一列都是按照从上到下递增的顺序排列 * 请设计一个方法,输入这样的一个二维数组和一个数字,判断这个数字是否存在于这个数组中 * */ public class Question4 { public static void main(String[] args) { // TODO Auto-generated method stub int[][] arr = new int[][] { {1, 3, 5, 7}, {2, 4, 6, 8}, {3, 5, 7, 9}, {4, 6, 8, 10} }; System.out.println(solution2(arr, 1)); } // 方法一: // 遍历整个二维数组进行查找 // 只提出方法一在面试中是完全不够的 public static boolean solution1(int[][] arr, int num) { try { for(int i = 0; i < arr.length; i++) { for(int j = 0; j <arr[0].length; j++) { if(arr[i][j] == num) { return true; } } } return false; } catch (Exception e) { e.printStackTrace(); return false; } } // 方法二: // 从右上角开始查找,给定值大于右上角,坐标下移一行,给定值小于右上角,坐标左移一行,相等,返回true,循环判断 // 左下角也可以,但是左上角与右下角不行 public static boolean solution2(int[][] arr, int num) { try { int row = 0; int col = arr[0].length-1; int std = arr[row][col]; while(row<arr.length-1 && col>=0) { if(std > num) {// 左移一列 std = arr[row][--col]; } else if(std < num) {// 下移一行 std = arr[++row][col]; } else { return true; } } return false; } catch (Exception e) { e.printStackTrace(); return false; } } }
转载请注明原文地址: https://www.6miu.com/read-2000178.html

最新回复(0)