剑指offer 面试题3 二维数查找 java实现

蔚落 2022-03-22 06:46 104阅读 0赞

面试题3：

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

分析：首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束：如果该数字大于要查找的数字，剔除这个数字所在的列：如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每－次都在数组的查找范围中剔除）行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

package partOne;
    
    public class FindMatrix {
        private boolean find(int[][] matrix,int value){
            //矩阵长度不符合要求
            if(matrix==null||matrix.length<1||matrix[0].length<1){
                return false;
            }
    
            int height = matrix[0].length;
            int length = matrix.length;
    
            int startHeight = height-1;
            int startLenght = 0;
            //确保查找的数据在数组中
            //初始查找比对数值为矩阵右上角值
           while(startHeight>0&&startLenght<length){
               int getvalue = matrix[startLenght][startHeight];
               if(matrix[startLenght][startHeight]==value){
                   System.out.println("查找的数值"+value+"是在第"+(startLenght+1)+"行，第"+(startHeight+1)+"列");
                   return true;
               }
               //右端的数据大于要找的数据，往左移一列
               if(matrix[startLenght][startHeight]>value){
                   startHeight--;
               }
               //右端的数据小于要找的数据，往下移一行
               if(matrix[startLenght][startHeight]<value){
                   startLenght++;
               }
           }
            System.out.println("数组中不存在该数");
           return false;
        }
    
        public static void main(String[] args) {
            int[][] testMar={
                    {1,2,3,5,5},
                    {2,3,4,5,6},
                    {2,5,6,7,8},
                    {9,10,11,12,13}
            };
            boolean ter = new FindMatrix().find(testMar,4);
    
    
            boolean ter1 = new FindMatrix().find(testMar,17);
           
    
    
        }
    }

打印的结果：（这个查找到的数据只是相对最右边的一个，如果数组中有多个相同的数据的话，需要优化一下，这里没有实现这个功能）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcnJ5cHR0ZXI_size_16_color_FFFFFF_t_70][] 代码github地址：[源码地址][Link 2]

[Link 1]: https://www.baidu.com/s?wd=%E5%88%97%E9%83%BD&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcnJ5cHR0ZXI_size_16_color_FFFFFF_t_70]: /images/20220322/ca4e7b903195471da58ff903c884a1d3.png
[Link 2]: https://github.com/harrypitter/Offer.git