剑指offer—二维数组中的查找 解答

剑指offer—二维数组中的查找

题目描述

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

思路

右上角或者左下角为起点,与target比较,相等返回

  • 左下角起点:target > 位置 则往右移, target < 位置 则往上移
  • 右上角起点:target > 位置 则往下移, target < 位置 则往左移

缩短了时间复杂度,不用遍历每一行的每一个,而是利用递增性质跳过一行的其他元素。

代码

  • 改代码以右上角为起点
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length<=1){//如果为空返回false
            return false;
        }
        int size = array.length-1;//最大下标
        int x = 0;//行的下标
        int y = size;//列的下标
        if(target<array[0][0]||target>array[size][size]){//比最小小或者比最大大,则返回false
            return false;
        }else{
            while((x<size+1)&&y>=0){//当行列下标满足边界值时循环
                if(target>array[x][y]){//数组值小的话,往下找,下面都比它大,可能等于target
                    x = x+1;
                }else if(target<array[x][y]){//数组值大的话,往左找,左边都比它小,可能等于target
                    y = y-1;
                }else{
                    return true;//相等,找到了,返回true
                }
            }
            return false;//没找到 返回false
        }
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/array-search.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!