《剑指Offer》面试题三之二维数组中的查找

2019-11-06 07:58:31

字体：大中小

来源：转载

供稿：网友

题目描述

在一个二维数组中，每一行都从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数！

解题思路

我们以下面的这个数组为例，判断其中是否有7这个数：测试数组我们观察这个数组会发现，数组任何位置上面的数的左边都小于这个数，下面的数都大于这个数。这时候我们可以寻找一个起始点来查找这个数：

如果从左上角开始，可以寻找的路为右和下，但是如果待查找的数大于该数，则无法知道选择哪一条路，故不能选择该起始点。当然选择右下角也是不行的。如果从右上角开始，如果待查找的数大于当前位置的数，则大于该数所在行左边的所有数，反之，则小于该数所在列下面的所有数，所以会有唯一的路走。当然，左下角也是可行的！

在该题中，我选择右上角开始：因为 9>7 ,所以查找范围变为：第一次查找后再次选择右上角，因为 8>7，查找范围变为：第二次查找后选择右上角，因为 9>7，查找范围变为：第三次查找后继续选择右上角，因为 4<7，则查找范围变为：第四次查找后这时候会发现，右上角的数就是待查找的数，算法运行完毕。

算法实现

import java.util.Scanner;/** * 剑指Offer面试题 DyadicArray.java * 作者：白芷 * 时间：2017/3/3 * 说明：二维数组中的查找 */public class DyadicArray { public static void main(String[] args) { int row, col;// 分别表示数组的行和列 int aim; //待查找的数 int[][] array; Scanner input = new Scanner(System.in); row = input.nextInt(); col = input.nextInt(); aim = input.nextInt(); array = new int[col][row]; for (int i = 0; i < col; i++) { for (int j = 0; j < row; j++) { array[i][j] = input.nextInt(); } } int rownum = 0; int colnum = col - 1;// 这两个是移动的游标 while (true) { if (array[rownum][colnum] > aim) {// 范围左移 colnum--; } else if (array[rownum][colnum] < aim) {// 范围下移 rownum++; } if (colnum < 0 || rownum >= row) {// 未查找到 System.out.PRintln("No"); break; } if (array[rownum][colnum] == aim) {// 查找到 System.out.println("Yes"); break; } } }}

上一篇：c简单位操作

下一篇：revert_by_date

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注