剣指Offer-2 D配列の検索

記録を作りましょう.何か間違いがあったら、みんなに指摘してもらいたいです.私が書いたのは簡単かもしれませんが、考えていないものもあるので、皆さんによろしくお願いします.ありがとうございます

テーマの概要

2 D配列では、各行が左から右に増加し、各列が上から下に増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.

入力および出力フォーマット

入力

入力には、各テストケースについて入力される第1の動作の2つの整数mおよびn(1<=m、n<=1000):入力するマトリクスの行数および列数を表す複数のテストサンプルが含まれる場合があります.入力された2行目には、検索する数値を表す整数t(1<=t<=1000000)が含まれます.次のm行は、各行にn個の数があり、問題が与えるm行n列を表す行列(行列は、問題記述に示すように、各行が左から右に増加する順序で並べ替えられ、各列が上から下に増加する順序で並べ替えられる.

しゅつりょく

各テストケースに対応して、出力「YES」は、2次元配列に数値tが見つかったことを表す.出力「NO」は、2次元配列に数字tが見つからないことを表す.

私の考え

私の考えでは、まず行数-1が下付きxであり、各行の個数yを見つけて、それから1つのカーソル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 

@interface SearchNumber : NSObject

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

@end

SearchNumber.m

#import "SearchNumber.h"

@implementation SearchNumber

-(BOOL)isExistNumber:(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 * array = [NSMutableArray array];
        while (1) {
            printf(" x  y 
");
            scanf("%ld %ld", &x, &y);
            if (x == 0 && y == 0) {
                break;
            }else{
                printf(" :
");
                scanf("%ld", &n);
                printf(" ：
");
                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配列を2次元配列と定義することはできず、配列をネストすることしかできないので、宣言します.(ルールに合っているかどうか分からないが、結局私も深く研究しなかった)

終わり、花を散らす!この考えが少し長く覚えてほしいですね~