二维数组中的查找

ゞ浴缸里的玫瑰 2024-02-19 12:46 4阅读 0赞

#### 文章目录 ####

*  题目描述
 *  代码
 *   *  我的思路
     *  别人的解法

## 题目描述 ##

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

## 代码 ##

### 我的思路 ###

在思考了行、列优先后，由于需要考虑的复杂度没有降低，都被我否定了；而后考虑的是对角优先：左上角开始计算。（?♀️思考需要深入，其实到这里就差一步，再拓展一下就会得到一个更好的解法了）

public class Solution {
        
        public boolean Find(int target, int [][] array) {
        
            // 确定数组的维度，考虑到来了行列不等的情况
            int rowsize = array.length;
            int colsize = array[0].length;
            int minsize = rowsize<colsize?rowsize:colsize;
            for(int i=0; i<minsize; i++) {
         // 以小的维度作为循环跳出条件（其实这里有一个遗漏的情况，题目中应该是考虑的维度相等（聪明的你自己看代码就能想到了，我就不废话了），所以也通过了）
                if(target==array[i][i]) return true; // 找到退出
                if(target<array[i][i]) {
         // 当前值大于target时
                    for(int j=2*(i-1); j<=2*i; j++) {
         // 此时需要考虑右上角到左下角的三个斜列
                    // 这三个斜列的每一个元素，都满足：横坐标+纵坐标=j
                        for(int k=0; k<=j; k++) {
        
                            if(j-k<colsize&&k<rowsize) {
         // 限制坐标>0且<维度
                               if(array[k][j-k]==target) {
        
                                return true;
                                }
                            }
                        }
                    }
                    return false;
                }
            }
            return false;
        }
    }

### 别人的解法 ###

由于我的解法代码比较复杂，还是需要考虑各种细致的情况，代码复杂度也比较高，故而搜索了一下大家的解法。

/*
    * 选取数组查找范围内的左下角的数字，如果该数字等于要查找的数字，则查找结束；
    * 如果该数字小于要查找的数字，则剔除该数字所在的列；
    * 如果该数字大于要查找的数字，则剔除该数字所在的行；
    */
    public class Solution {
        
        public boolean Find(int target, int [][] array) {
        
            int rows = array.length;
            int cols = array[0].length;
            int i=rows-1,j=0;
            while(i>=0 && j<cols){
        
                if(target<array[i][j])
                    i--;
                else if(target>array[i][j])
                    j++;
                else
                    return true;
            }
            return false;
        }
    }

上面给出的是左下角到右上角的搜索，同理，右上角到左下角的搜索也是可以的。

[相关文章][Link 1],代码有略微差异，思路是相同的。

[Link 1]: https://www.cnblogs.com/gl-developer/p/6431331.html