二维数组中的查找（Java实现）

清疚 2023-07-13 10:56 7阅读 0赞

## 二维数组中的查找（Java实现） ##

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

1 2 8 9
    2 4 9 12
    4 7 10 13
    6 8 11 15

中，查找数字7，返回true；查找数字5，返回false.  
**题解:**  
首先，我们来谈一下最为直观的解，就是遍历一遍二维数组，时间复杂度o(n\*m)，空间复杂度o(1)。当然这个时间复杂度是不足以拿offer的。我们再来看看时间复杂度为o(n)，空间复杂度微o(1)的算法。

当我们需要解决一个比较复杂的问题时，一个很有效的办法就是从一个具体的问题入手，通过分析简单具体的例子，试图寻找普遍的规律。  
比如数组：

1 2 8 9
    2 4 9 12
    4 7 10 13
    6 8 11 15

我们寻找7。直接的想法从左上角开始找，1小于7.那么7肯定会在1的右边或者下边。这个时候有三个区域。右边区域，下边区域和右边与下边重叠的区域，不好确定接下来该怎么搞。我们再试试从左上角开始。9大于7,那么7就只能在9的左边，不可能在9在的当前列。那么可以排除9这一列。继续找左上角，是8。8大于7排除8在的当前列。继续找左上角2。发现2小于7，那么肯定在2的下面，排除2所在的当前行。继续找左上角，找到4，发现4小于7，排除4所在的当前行。继续左上角，发现是7.找到返回。该算法每次都能排除一行或者一列。所以时间复杂度是o(n+m)，空间复杂度是o(1)。

根据题目的特点，从一个具体的案例去分析，找出优解。

package Day39;
    
    import java.util.Scanner;
    
    /** * @Author Zhongger * @Description 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序， * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数 * @Date 2020.3.11 */
    public class FindInMatrix { 
        public static void main(String[] args) { 
            int[][] matrix = new int[4][4];
            int number=7;
            Scanner scanner = new Scanner(System.in);
            for (int i = 0; i < matrix.length; i++) { 
                for (int j = 0; j < matrix[0].length; j++) { 
                    matrix[i][j]=scanner.nextInt();
                }
            }
            FindInMatrix findInMatrix = new FindInMatrix();
            System.out.println(findInMatrix.findInMatrix(matrix, number));
    
        }
    
        /** * 查找方法 * @param matrix 二维数组 * @param number 待查找的数字 * @return */
        private boolean findInMatrix(int[][] matrix,int number){ 
            boolean isFind=false;
            int rows = matrix.length;//行数
            int columns = matrix[0].length;//列数
            int i=0;//行
            int j=columns-1;//列
            while (i<rows&&j>=0){ 
                if (matrix[i][j]==number){ 
                    isFind=true;
                    break;
                }
                else if (matrix[i][j]>number){ 
                    j--;
                }
                else { 
                    i++;
                }
            }
            return isFind;
        }
    }

剑指Offer上的原题，从今天开始我会每天更新算法题解，敬请关注！**另外，我这里有深入理解Java虚拟机（第三版）的电子版资源，需要的话可以添加我的微信973593026.**