做個記錄吧，有什么錯誤，希望大家?guī)兔χ刚幌?。可能我寫的比較簡單，有的東西沒有考慮到，也希望大家多多指正。謝謝啦~
題目概述
在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
輸入和輸出格式
輸入
輸入可能包含多個測試樣例，對于每個測試案例，
輸入的第一行為兩個整數(shù)m和n(1<=m,n<=1000)：代表將要輸入的矩陣的行數(shù)和列數(shù)。
輸入的第二行包括一個整數(shù)t(1<=t<=1000000)：代表要查找的數(shù)字。
接下來的m行，每行有n個數(shù)，代表題目所給出的m行n列的矩陣(矩陣如題目描述所示，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。
輸出
對應每個測試案例，
輸出”YES”代表在二維數(shù)組中找到了數(shù)字t。
輸出”NO”代表在二維數(shù)組中沒有找到數(shù)字t。
我的思路
我的思路，先找出行數(shù)-1即是下標x，每行的個數(shù)y，然后一個游標n從0開始，從最后一排開始。因為矩陣是有序的，當array[x][n]大于目標值num的時候，證明該往上一行，x-1；當array[x][n]小于目標值num的時候，證明改行該向后移動，即n++；當array[x][n]的時候，返回true；循環(huán)終止時，返回false。
因為矩陣有序，所以大概應該是這個樣——
1 2 3
4 5 6
7 8 9
首先來一個死的思路，數(shù)據(jù)都寫死試一試
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);
}
發(fā)現(xiàn)好像對。下面在來一個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("輸入查找的數(shù)字:\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的數(shù)組中只能存儲對象，所以要用NSNumber，同樣OC中原生的OC數(shù)組不能定義稱為二維數(shù)組，只能嵌套數(shù)組，所以那么聲明。（不知道合不合規(guī)矩，結果對了我也沒深究）
