(OC)
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否存在该整数。 如5不存在，7存在
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 16
我的想法是从右上角开始比较，如果右上角的数字大于给定的数字，则最后一列不用进行比较；如果小于，则第一行不用比较；相等直接返回；依次类推。
BOOL findNumber(NSArray <NSArray *> *matrix, int number, int row, int column) {
if (row < 0 || column < 0 || row > matrix.count - 1 || column > matrix[0].count - 1) {
return NO;
}
if ([matrix[row][column] intValue] == number) {
return YES;
}else if ([matrix[row][column] intValue] < number) {
return findNumber(matrix, number, row + 1, column);
}else {
return findNumber(matrix, number, row, column - 1);
}
}
BOOL find(NSArray <NSArray *> *matrix, int number) {
if (!matrix.count) {
return NO;
}
if (!matrix[0].count) {
return NO;
}
return findNumber(matrix, number, 0, (int)matrix[0].count - 1);
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
BOOL result = find(@[@[@1, @2, @8, @9], @[@2, @4, @9, @12],@[@4, @7, @10, @13],@[@6, @8, @11, @16]], 17);
NSLog(@"%d", result);
}
return 0;
}
