问题描述：在一个二维数组上，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
查找9时，打印查到了；
查找5时，打印未查到。
分析：
首先选取数组中右上角的数字。如果该数字等于要查找的数字，查到了，列数递减，继续循环；如果该数字大于要查找的数字，剔除这个数字所在列；如果该数字小于要查找的数字，剔除这个数字所在的行。
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view, typically from a nib.
NSArray *array=@[@[@1,@2,@8,@9],@[@2,@4,@9,@12],@[@4,@7,@10,@13],@[@6,@8,@11,@15]];
/*
打印原数组
*/
NSString *oldArrayStr = @"\n";
for (int row=0; row<array.count; row++) {
NSArray *oneArray = array[row];
for (int column=0; column<oneArray.count; column++) {
oldArrayStr = [oldArrayStr stringByAppendingString:@" "];
NSNumber *currentNumber = oneArray[column];
oldArrayStr = [oldArrayStr stringByAppendingString:currentNumber.description];
}
oldArrayStr = [oldArrayStr stringByAppendingString:@"\n"];
}
NSLog(@"%@",oldArrayStr);
/*
调用查找函数
*/
BOOL found = [self findNumber:5 withArray:array rows:4 columns:4];
NSLog(@"found %@",found?@"查到了":@"未查到");
}
-(BOOL)findNumber:(NSInteger)number withArray:(NSArray *)array rows:(NSInteger)rows columns:(NSInteger)columns {
BOOL found = NO;
NSInteger row=0;
NSInteger column = columns - 1;
while (row<rows && column >= 0) {
NSArray *oneArray = array[row];
NSNumber *currentNumber = oneArray[column];
if (currentNumber.integerValue == number) {
found = YES;
NSLog(@"row %ld column %ld",row,column);
// break;
//删除列
column = column - 1;
} else if (currentNumber.integerValue > number) {
//删除列
column = column - 1;
} else {
//删除行
row = row + 1;
}
}
return found;
}
调用函数查找5,运行：
2018-12-18 13:43:43.706342+0800 GCDDemo[75603:17623605]
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
2018-12-18 13:43:43.706539+0800 GCDDemo[75603:17623605] found 未查到
调用函数查找9,运行：
2018-12-18 13:54:26.986167+0800 GCDDemo[75764:17629506]
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
2018-12-18 13:54:26.986270+0800 GCDDemo[75764:17629506] row 0 column 3
2018-12-18 13:54:26.986342+0800 GCDDemo[75764:17629506] row 1 column 2
2018-12-18 13:54:26.986421+0800 GCDDemo[75764:17629506] found 查到了