二维数组中的查找

发表于

面试题4：二维数组中的查找

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

OC形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
...
NSArray *array = @[
      @[@1,@2,@8,@9],
      @[@2,@4,@9,@12],
      @[@4,@7,@10,@13],
      @[@6,@8,@11,@15]
  ];
  BOOL result = [self findWithArray:array rows:4 columns:4 number:7];
  ...
- (BOOL)findWithArray:(NSArray *)matrix rows:(int)rows columns:(int)columns number:(int)number {
    BOOL found = NO;
  
    if (matrix != nil && rows > 0 && columns > 0) {
        int row = 0;
        int column = columns - 1;
        while (row < rows && column > 0) {
            if ([matrix[row][column] intValue] == number) {
                found = YES;
                break;
            }else if ([matrix[row][column] intValue] > number){
                -- column;
            }else {
                ++ row;
            }
        }
    }
    return found;
}

思路

每次都选取数组查找范围内的右上角数字，也可以选取左下角数字。但不能选左上角数字或右下角数字因为无法剔除所在行或者列，无法缩小查找范围。