牛客网-二维数组的查找

柔光的暖阳◎ 2023-03-01 03:18 13阅读 0赞

# 题目描述 #

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

//解决思路:
    //如数组样式如下:
    // 1 2 3 4
    // 2 3 4 5
    // 3 4 5 6
    //正常查找的过程,本质就是排除的过程,如果双循环查找,本质是一次排除一个,效率过低
    //根据题面要求,我们可以采取从右上角(或左下角)进行比较(想想为什么?),这样可以做到一次排除一行或者一列

# 1、忽略时间空间复杂度，直接遍历，暴力解法 #

public class Solution { 
        public boolean Find(int target, int [][] array) { 
             for (int[] ints : array) { 
                for (int anInt : ints) { 
                    if(anInt==target)
                        return true;
                }
            }
    
            return false;
        }
    }

# 2、优化解法，考虑时间和空间复杂度 #

看到查找应该，就是想尽办法去排除。

查找的过程中你排除的越多，你的算法也就越快。

`根据题面要求,我们可以采取从右上角(或左下角)进行比较(想想为什么?),这样可以做到一次排除一行或者一列`

if(array==null)
                return false;
    
            int i = 0,//i：指向每一行最小的值
                j=array[0].length-1;//j：指向每一行最大的值
    
            while (i < array.length && j >=0 ){ 
    
                //此时array[i][j] 一定这一行最大的
                if(target < array[i][j]){ 
                    j--;//如果比这一行的最大值小，指向这一行最大值的指针j就j-1,移动下一个元素
    
                //如果查找的数大于这个最大值，就说明肯定是在这一列，那么就i++就可以继续找这一列了
                }else if (target > array[i][j]){ 
                    i++;
    
                //查找成功返回true
                }else{ 
                    return true;
                }
            }
    
            return false;