剑指offer4:二维数组中的查找

╰+哭是因爲堅強的太久メ 2022-02-19 05:17 175阅读 0赞

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

1.首先题目的每一行从左到右依次递增，每列从左到右依次递增，这样本身就是一个可以利用的隐含条件。

2.题目的切入点很艹蛋的妙，从右上角做为起始点，每次比较如果查找的值比当前数组的值大，那么这一列减少，如果查找的值比当前数组的值小，则当前行+1(行从0开始),如果等于，则返回true，break.

总结：刚开始想到的是深度遍历，还是自己太菜了。善于发现规律，从普通例子入手。这也是题目想考核的点。

附上代码

package com.hnist.lzn.jinazhioffer;
    
    public class Lookforinlist {
    
        boolean Look(int[][] nums,int rows,int columns,int number){
    
            //在一个二维数组中查找对应的值,行列都是递增的
            boolean index = false;
    
            if(nums!=null&&rows>0&&columns>0){
    
                int row = 0;
    
                int column = columns-1;
                //为啥这样呢
                while(row<rows&&column>=0){
    
                    if(nums[row*column][column]==number){
    
                        index = true;
                        break;
                    }
                    else if(nums[row*column][column]>number){
    
                        --column;
                    }else{
                        ++row;
                    }
    
    
                }
    
            }
    
    
                return index;
    
        }
    
        public static void main(String[] args) {
    
            int[][] nums = {
       {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
    
            System.out.println(new Lookforinlist().Look(nums,4,4,7));
    
        }
    
    }