4

二维数组中的查找

 2 years ago
source link: https://zhangslob.github.io/2019/12/29/%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E6%9F%A5%E6%89%BE/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client 
这是崔斯特的第一百零九篇原创文章

努力、奋斗 (๑• . •๑)

二维数组中的查找

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

例如下面的二维数组，如果查找7，返回true，查找5，返回false。

1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15

寻找目标数字b，从数组中选一个数字a，如果a=b，结束查找；如果a>b，那么接下来查找的范围就是a的左边或上边；如果a<b，那么接下来搜索范围就是右边或下边。

当我们需要解决一个复杂的问题时，一个很有效的方法就是从一个具体的问题入手。本题可以从查找数字7入手，一步步分析过程。如果我们在二维数组中间随机选一个数字，那么下次搜索范围就是两个区域，而且有重叠。如果从数组的某一个角上开始搜索，就不会遇到这个问题。

比如从数组右上方开始，

  1. a=9，b=7，a>b，接着查找左边和上边，由于没有上边，所以只能查找左边，也就是1、2、8这三列
  2. a=8，a>b，接着查找左边和上边，因为没有上边，只能接着找左边，也就是1，2这两列
  3. a=2，a<b，接着就是右边和下边，右边已经查找过，所以接下来就是一直往下查找，也就是1、2这两列的下方
  4. a=4，a<b，接着查找1、2这两列的下面两行
  5. a=7，a=b，结束查找。

从二维数组的右上方开始查找：

  • 若元素值等于 target，返回 true；
  • 若元素值大于 target，砍掉这一列，即 --j；
  • 若元素值小于 target，砍掉这一行，即 ++i。

也可以从二维数组的左下方开始查找，以下代码使用左下方作为查找的起点。

注意，不能选择左上方或者右下方的数字，因为这样无法缩小查找的范围。

public class Solution {
public boolean find(int target, int[][] array) {
if (array == null) {
return false;
int rows = array.length;
int columns = array[0].length;
int i = rows - 1;
int j = 0;
while (i >= 0 && j < columns) {
if (array[i][j] == target) {
return true;
if (array[i][j] < target) {
} else {
return false;
public static void main(String[] args) {
int[][] arr = new int[][]{
{1, 2, 8, 9},
{2, 4, 9, 12},
{4, 7, 10, 13},
{6, 8, 11, 15}
boolean res = new Solution().find(7, arr);
System.out.println(res);

如果是我自己去写这道题的话，肯定想不出这样的方法，可能就是遍历所有数字，这肯定不是面试官要问的。看了书中介绍的方法，分析过程确实很重要，一步步去寻找规律。我想起了高中数学的数列，老师常说“数列就是列数，如果不知道规律，就多写几个例子”。对于现在的这种算法题，一定要多试几个例子，从中找到规律。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK