首页 > 代码库 > 九度 1384 二维数组中的查找

九度 1384 二维数组中的查找

 

#include<cstdio>#include<iostream>using namespace std;#define NMAX 1000010int arr[NMAX];/** * 只需要从左下角或右上角开始查找,即可。 * 当是从右上角开始查找时, * 左上角(row = 0,column = columns - 1), * 1)若查找的值key大于当前的值arr[i],则说明key在此行以下,故有row++; * 2)若查找的值key小于当前的值arr[i],则说明key在此列的左边,故有column--; * 3)若相等,则返回true * 4)判断条件:row<rows && column >=0,若满足,继续1),若不满足,则直接返回false */bool query(int rows, int columns, int key) {    bool flag = false;    int column = columns - 1;    int row = 0;    while (row < rows && column >= 0) {        int temp = arr[row * columns + column];        if (temp == key) {            flag = true;            return flag;        } else if (temp > key) {            column--;        } else {            row++;        }    }    return flag;}/** * 当是从左下角开始查找时, * 左上角(row = rows - 1,column = 0), * 1)若查找的值key小于当前的值arr[i],则说明key在此行以下,故有row--; * 2)若查找的值key大于当前的值arr[i],则说明key在此列的左边,故有column++; * 3)若相等,则返回true * 4)判断条件:row >= 0 && column < columns,若满足,继续1),若不满足,则直接返回false */bool query1(int rows, int columns, int key) {    bool flag = false;    int column = 0;    int row = rows - 1;    int temp = -1;    while (row >= 0 && column < columns) {        temp = arr[row * columns + column];        if (temp == key) {            flag = true;            return flag;        } else if (temp > key) {            row--;        } else {            column++;        }    }    return false;}int main() {    int n, m, t, len;    bool flag;    while (~scanf("%d%d%d", &n, &m,&t)) {        len = n * m;        for (int i = 0; i < len; i++) {            scanf("%d", arr + i);        }        flag = query1(n, m, t);        if (flag) {            printf("Yes\n");        } else {            printf("No\n");        }    }    return 0;}

 

九度 1384 二维数组中的查找