面试题04:二维数组中的查找

原创
2020/02/17 22:03
阅读数 136

题目描述

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

思路

  1. 通过每一行从左到右都是递增的,每一列从上到下也是递增的,可以去通过比较数字大小,来删除某一列或者某一个行。
  2. 将二维数组想象成矩阵。从数组的右上角数字 m 开始。
  3. 如果 m == target,那么说明数组中含有该整数,直接返回 true。
  4. 如果不相等,那么继续比较。
  5. 如果 m > target 成立,那么根据题意,m 所在那一列的所有数字都是比 target 大的,那么可以去除该列,然后继续取右上角的数字为 m。
  6. 如果 m < target 成立,那么根据题意,m 所在哪一行的所有数字都是比 target 小的,那么可以去除该行,然后继续取右上角的数字为 m。
  7. 去反复判断,直至所有的数字都不等于 target,那么返回 false。

代码

public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array == null || array.length <= 0 || array[0].length <= 0) {
            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--;
            } else {
                // 去除该行
                row++;
            }
        }
        
        return false;
    }
}
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部