淘先锋技术网

首页 1 2 3 4 5 6 7

1.题目:

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

2.示例:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。

给定 target = 20,返回 false。

3.解题思路:

本题可以从左上角或者右下角入手。

从矩阵的左下角看,上方的数字都比其小,右方的数字都比其大,所以依据该规律去判断数字是否存在
设当前数字为 n,目标数字为 target,当 target < n 时,n 更新为其上面的数字,当 target > n 时,n 更新为其右侧的数字,直到相等则返回 true,否则到了矩阵边界返回 false。

右上角同理;

设当前数字为 n,目标数字为 target,当 target < n 时,n 更新为其左面的数字,当 target > n 时,n 更新为其下面的数字,直到相等则返回 true,否则到了矩阵边界返回 false。

4.题解(左下)

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){
   if(matrixSize==0||*matrixColSize==0){
       return false;
   }
   int h = matrixSize-1;
   int l = 0;
   while(l<*matrixColSize && h>=0){
       if(matrix[h][l]<target){
           l++;
       }else if(matrix[h][l]>target){
           h--;
       }else{
           return true;
       }
   }
   return false;
}

右上:

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){
    if (matrixSize == 0 || *matrixColSize == 0)
    {
        return false;//数组为空,返回false
    }
    int h = 0;//行
    int l = *matrixColSize - 1;//列
    while(h < matrixSize && l >= 0)
    {
        if (matrix[h][l] < target)
        {
            h++;//如果target比较大,说明target在下行
        }
        else if (matrix[h][l] > target)
        {
            l--;//如果target比较小,说明target在前列
        }
        else
        {
            return true;
        }
    }
    return false;
}