【两日一练】学习记录

题目

1. 在一个二维数组中，每行都按照从左至右递增的顺序排列，每列都按照从上至下递增的顺序排列。请编写一个函数，输入一个如上所述的二维数组和一个整数，判断数组中是否含该整数。例如，下面的二维数组就是每行、每列都递增排列的。如果在这个数组中查找数字7，那么返回true；如果查找数字5，那么由于该数组中不含有该数字，返回false。

思路

首先从后往前进行查找，如果第1行、第4列的数字比7大，那么比较第1行第3列的数字，如果发现还是比7大，那么就比较第1行、第2列的数字，这个数字比7小，这时开始比较第2行、第2列，最终找到与7相等的数字。这个题目考的是逆向思维法，从后往前比，可以减少比较次数。

代码

#include <stdio.h>
#include <stdlib.h>

int Find(int* matrix,int rows,int columns,int number)
{
    int found=0;
    if(matrix!=NULL && rows>0 && columns>0)
    {
        int row=0;
        int column=columns-1;
        while(row<rows && column>=0)
        {
            if(matrix[row*columns + column] == number)
            {
                found=1;
                printf("the munber %d is in row: %d and column: %d\n",number,row+1,column+1);
                break;
            }
            else if(matrix[row*columns + column] > number)
                --column;//列数减
            else
                ++row;//行数加
        }
    }
    return found;
}


int main()
{
    int rows=4;//存储行数
    int columns=4;//存储列数
    int number=7;//查找的数字
    int matrix[][4]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
    int i,j,result;//i,j用于打印二维数组
    for(i=0;i<rows;i++)
    {
        for(j=0;j<columns;j++)
        {
            printf("%d\t",matrix[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    result=Find((int*)matrix,rows,columns,number);
    if(result)
        printf("found.\n");
    else
        printf("not found.\n");
    system("pause");
    return 0;
}

执行结果