剑指Offer——二维数组中的查找

做个记录吧，有什么错误，希望大家帮忙指正一下。可能我写的比较简单，有的东西没有考虑到，也希望大家多多指正。谢谢啦~

题目概述

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

输入和输出格式

输入

输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为两个整数m和n(1<=m,n<=1000)：代表将要输入的矩阵的行数和列数。
输入的第二行包括一个整数t(1<=t<=1000000)：代表要查找的数字。
接下来的m行，每行有n个数，代表题目所给出的m行n列的矩阵(矩阵如题目描述所示，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

输出

对应每个测试案例，
输出”YES”代表在二维数组中找到了数字t。
输出”NO”代表在二维数组中没有找到数字t。

---

我的思路

我的思路，先找出行数-1即是下标x，每行的个数y，然后一个游标n从0开始，从最后一排开始。因为矩阵是有序的，当array[x][n]大于目标值num的时候，证明该往上一行，x-1；当array[x][n]小于目标值num的时候，证明改行该向后移动，即n++；当array[x][n]的时候，返回true；循环终止时，返回false。

因为矩阵有序，所以大概应该是这个样——

1  2  3 
4  5  6
7  8  9

首先来一个死的思路，数据都写死试一试

bool isExist(int array[][1000], int target){
    int i = 2;
    int j = 3;
    int n =0;
    while (i > 0 && n < j) {
        if (array[i][n] < target) {
            n++;
        }
        if (array[i][n] > target) {
            i--;
        }
        if (array[i][n] == target) {
            NSLog(@"YES");
            return true;
        }
    }
    NSLog(@"NO");
    return false;
}
void test(){
    int array[1000][1000] = {{1,2,3}, {4,5,6}, {7,8,9}};
    int target = 11;
    
    bool result = isExist(array, target);
    NSLog(@"%d", result);
}

发现好像对。下面在来一个OC封装的。

SearchNumber.h

#import <Foundation/Foundation.h>

@interface SearchNumber : NSObject

-(BOOL)isExistNumber:(NSArray<NSArray*> *)array target:(NSInteger)target;

@end

SearchNumber.m

#import "SearchNumber.h"

@implementation SearchNumber

-(BOOL)isExistNumber:(NSArray<NSArray *> *)array target:(NSInteger)target{
    NSInteger i = array.count-1;
    NSInteger j = array[0].count;
    NSInteger n = 0;
    while (i > 0 && n  < j) {
        if ([[array[i] objectAtIndex:n] integerValue] == target) {
            return YES;
        }else if ([[array[i] objectAtIndex:n] integerValue] > target) {
            i--;
        }else if ([[array[i] objectAtIndex:n] integerValue] < target) {
            n++;
        }
    }
    return NO;
}

@end

main.m

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSInteger n = 0;
        NSInteger x = 0, y = 0, num;
        NSMutableArray<NSArray *> * array = [NSMutableArray array];
        while (1) {
            printf("输入行x 和列y \n");
            scanf("%ld %ld", &x, &y);
            if (x == 0 && y == 0) {
                break;
            }else{
                printf("输入查找的数字:\n");
                scanf("%ld", &n);
                printf("输入矩阵：\n");
                for (NSInteger i = 0; i < x; i++) {
                    NSMutableArray * arr = [NSMutableArray array];
                    for (NSInteger j = 0; j < y; j++) {
                        scanf("%ld", &num);
                        [arr addObject:[NSNumber numberWithInteger:num]];
                    }
                    [array addObject:arr];
                }
                SearchNumber * searchNum = [[SearchNumber alloc] init];
                BOOL result = [searchNum isExistNumber:array target:n];
                if (result) {
                    NSLog(@"存在");
                }else{
                    NSLog(@"不存在");
                }
            }
        }
    }
    return 0;
}

由于OC的数组中只能存储对象，所以要用NSNumber，同样OC中原生的OC数组不能定义称为二维数组，只能嵌套数组，所以那么声明。（不知道合不合规矩，结果对了我也没深究）

---

完结，撒花！希望这个思路能记得长一点~