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

时间限制:1秒 空间限制:32768K

解析:

我们首先可以判断出这是一个有序数组,类似于

1 2 3 4
5 6 7 8
9 10 11 12

 

一开始我们用最笨的方法暴力遍历算法,两个循环嵌套,时间超时。

然后开始看着这个二维数组,在它的右上角是这一行的最大值,这一列的最小值,同理左下角是这一行的最小值,这一列的最大值。因此我们可以将元素定位到这个点,我们以右上角为例,当输入进来的元素大于这个值时,那么一定在这一行的 下面所以

行++,当这个值小于时一定在这个值的左边,列--。

继而c++代码如下

class Solution
{
    public bool Find(int target, int[][] array)// 
    {
       int col=array[0].Length-1;
        int row=0;
        while(row<=array.Length-1&&col>=0)
        {
            if(target>array[row][col])
                row++;
            else if(target==array[row][col])
                return true;
            else
              col--;
        }
        return false;
    }
}

第二种方法是二分法,我们可以把每一行都当做一个有序数组,二分法顾名思义,取半对折,排序完成后后找到中间的那个,与输入的值进行比较当大于输入值时,就留下大的那一半,继续进行对半直到找到相等的元素。

分析如下,输入的是array[] [],通过array.Length,求出行的长度,array[i].Length是在第i行下列的长度

代码如下:

public boolean Find(int target, int [][] array) {
    for(int i=0;i<array.length;i++){
            int low=0;
            int high=array[i].length-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(target>array[i][mid])
                    low=mid+1;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    return true;
            }
        }
        return false;
    }