1.二维数组中的查找

题目:

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

解题思路:

1.首先,我们可以利用此题的特性“每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序”。

2.我们可以想到每次都从右上角那个数进行比较。

3.先从列开始,原因:因为最右边的列的数必定是每一行的最大值,基于这个条件,我们可以作出比较。

4.如果需要查找的数比右上角的数小,那么必定不能在此列中往下走,所以col--。

5.在列的判断基础上,如果查找的数比右上角的数大,那么我们的行只能往下走,去寻找那个更大的值,row++。

6.当列和行条件不符合要求时,返回false。

注:读者若看不懂,可以在留言区讨论,楼主会常来此地。

图解:

              

(1)查找数为9,此时右上角的数为12,故列往左移动一列。                           

     

(2)蓝色一行已经删除,此时右上角的数为7,比9小,故行往下移动一行。

          

(3)黄色行删除,此时右上角的数为10,比9大,故列往左移动一列。                                                         

    

(4)蓝色行删除,此时右上角的数为6,比9小,故行往下移动一行。 

   

(5)黄色行删除,此时右上角的数为8,比9小,故行往下移动一行。                                                         

      

(6)黄色行删除,此时右上角的数为9,为查找数,故返回true。

 JAVA代码实现:

public class Solution {
    public boolean Find(int target, int [][] array) {
        //先从右上方开始查找
        int row = 0;
        int col = array[0].length - 1;
        while (row < array.length && col >= 0) {
            if (target == array[row][col]) {
                return true;
            } else if (target < array[row][col]) {
                col--;     //往左走
            } else {
                row++;  //往下走
            }
        }
        return false;
    }
}

  

原文地址:https://www.cnblogs.com/sanjun/p/7924085.html