美文网首页
面试题4:二维数组中的查找

面试题4:二维数组中的查找

作者: 潘雪雯 | 来源:发表于2020-05-09 20:53 被阅读0次

    题目

    在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
    举例:下面的二维数组每行、每列都递增排序。若在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。


    image.png

    解题思路

    1. 首先选取数组右上角的数字9.因为数组中每一行都按照从左到右递增,每一列从上到下递增。所以7<9,也就是7不可能出现在9所在的列,故把这一列踢出。同理,可以把9对应的列也剔除
    2. 这样剩余的两列组成的数组中,数字2位于数组的右上角,因为右边已没有元素,所以7只能在2的下边,可以把2对应的行剔除。同理把4对应的行剔除
    3. 在剩余的两行两列中,刚好位于右上角的是需要查找的数字7

    代码

    • 细节
    1. 二维数组的初始化
    int matrix[][4]={{1,2,8,9},
                        {2,4,9,12},
                        {4,7,10,13},
                        {6,8,11,15}};
    
    1. 二维数组为函数参数退化为数组的指针(一维数组指针)
    一维数组 char a[30]             指针 char*
    指针数组 char *a[30]            指针的指针 char **a
    二维数组 char a[10][30]         数组的指针 char(*a)[30]
    
    1. 代码
    class Solution{
      public:
        bool numInmatrix(int *matrix,int num,int rows,int columns)
        {
            bool found = false;
            if(matrix != NULL && rows>0 && columns >0)
            {
                int row = 0;
                int column = columns-1;
                while(row<rows && column >=0)
                {
                    if(matrix[row*columns+column] == num)
                    {
                        found = true;
                        break;
                    }
                    else if(matrix[row*columns+column] > num)
                    {
                        --column;
                    }
                    else
                    {
                        ++row;
                    }
                }
            }
            return found;
        }
    };
    

    完整代码见Github

    相关文章

      网友评论

          本文标题:面试题4:二维数组中的查找

          本文链接:https://www.haomeiwen.com/subject/dwjlnhtx.html