剑指Offer-二维数组查找

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

解题思路1：先使用二分法定位筛选掉不可能的区间，再使用二分法分行查询每一个一维数组

public static boolean findTarget(int target, int [][] array) {

        if(array.length==0){

            return false;

        }

        int rows = array.length;

        int cols = array[0].length;

        if(target<array[0][0] || target>array[rows-1][cols-1]){

            return false;

        }

        //先确定在哪一行

        int middle = 0, low = 0, high = rows-1;

        while (high>low){

            middle = (low + high) / 2;

            if(array[middle][0] > target)

                high = middle - 1;

            else if(array[middle][0] < target)

                low = middle + 1;

            else

                return true;

        }

        for(int x=0;x<high;x++){

            while (array[x][cols-1]<target)

                x++;

            low = 0;

            high = cols -1;

            while (high>=low){

                middle = (low + high)/2;

                if(array[x][middle] > target)

                    high = middle - 1;

                else if(array[x][middle] < target)

                    low = middle + 1;

                else

                    return true;

            }

        }

        return false;

    }

解题思路2：根据二维数组的有序性，从第一行开始比较最后一位数和目标值的大小，如果目标值小叫筛选掉这一列(列索引减一)

public static String findTarget2(int target, int[][] array){

        if(array.length==0 || array[0].length == 0){

            return "-1";

        }

        int rows = array.length;

        int cols = array[0].length;

        if(target<array[0][0] || target>array[rows-1][cols-1]){

            return "-1";

        }

        int x = 0, y = cols - 1;

        while (x<rows && y>=0){

            if(array[x][y] == target)

                return "坐标是:["+x+" ]["+y+"]";

            else if(array[x][y] > target)

                y--;

            else

                x++;

        }

        return "-1";

    }

巴特西

剑指Offer-二维数组查找

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

最新文章

热门文章