【剑指offer第二版】面试题4

红太狼 2022-02-27 23:46 219阅读 0赞

转载自[https://blog.csdn.net/weixin\_37672169/article/details/79979484][https_blog.csdn.net_weixin_37672169_article_details_79979484]

--------------------

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

2 4 9 12

4 7 10 13

6 8 11 15

分析：  
首先我们选取数组右上角的数字9.由于9大于7，并且9还是第4列的第一个（也是最小的）数字，因此7不可能出现在数字9所在的列，于是只需要分析剩下的3列，在剩下的矩阵中，位于右上角的数字还是8.同样8大于7，因此8所在的列也可以剔除。接下来只需分析剩下的两列，由于2小于7，那么要查找的7可能在2的右边和下边。由于2的右边都已经被剔除，所以只可能出现在2的下边，将2所在的行剔除，只剩下三行两列，再和前面同样的方法查找，当找到7时就结束了。  
总结规律如下：首先选取矩阵右上角的数字。如果等于要查找的数字，查找过程结束；如果大于要查找的数字，则剔除这个数字所在的列，如果小于要查找的数字，则剔除这个数字所在的行。这样每一步都可以缩减查找范围，直到找到要查找的数字，或者查找失败。

public class Solution {
        /**
         * 二维数组的查找
         * @param arr
         *            已知的数组
         * @param number
         *            带查找的数
         * @return
         */
        public static boolean find(int arr[][], int number) {
            boolean flag = false;
    
            //既不是null，也不是空数组
            if (arr != null && arr.length != 0){
                int rows = arr.length; // 行数
                int columns = arr[0].length; // 列数
    
                //当前的行和列
                int row = 0;
                int column = columns - 1;
    
                while (row <= rows - 1 && column >= 0) {
                    // 比较二维数组中元素与number的关系
                    if (arr[row][column] == number) {
                        flag = true;
                        break;
                    } else if (arr[row][column] > number) {
                        column--;
                    } else {
                        row++;
                    }
                }
            }
            return flag;
        }
    
        public static void main(String args[]) {
            // 测试用例
            int array[][] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
            boolean flag = find(array, 15);
            System.out.println(flag);
        }
    }

[https_blog.csdn.net_weixin_37672169_article_details_79979484]: https://blog.csdn.net/weixin_37672169/article/details/79979484