原题链接

描述

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

示例

输入： 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
说明： 存在7，返回true

思路

如下图所示，这个数组元素规律性很强。左边的数小于右边的，下边的数小于上边的。

所以从右上角的数S开始比对检测，若target小于S，那么左移；若target大于S，下移一行。

这里的行、列变换还可以用二分查找的思想。。想起来的话再写吧。

解答

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length==0 || array[0].length==0){
            return false;
        }
        int a = array.length;
        int b = array[0].length;
        int i = 0, j=b-1;
        while(target != array[i][j]){
            if(i<=a-1 && j>=0){
                if(target > array[i][j])
                    i++;
                else if (target < array[i][j])
                    j--;
            }
            if(i>a-1 || j<0)
                return false;
        }
        return true;
    }
}

更

package com.klaus.array.prob4;

import org.junit.Test;

public class Solution {
    /**
     * <p>暴力</p>
     * 每行最后一个都是最大的，target和行最大元素比较
     * 如果大于，向下一行
     * 如果小于，向左一列
     * 直至相等或越界
     *
     * @param matrix 二维数组
     * @param target 待寻找元素
     * @return 是否存在
     */

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = 0, j = cols - 1;
        while (i < rows && j >= 0 ) {
            if (target > matrix[i][j]) ++i;
            else if (target < matrix[i][j]) --j;
            else return true;
        }
        return false;
    }
}