0%

剑指Offer算法题-有序二维数组查找

Posted on In

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

实现思路: 由于这个二维数组是每行有序，每列有序。所以可以这样

  1. 可以每次选取二维数组中，右上角的数字。
  2. 若该数字等于该查找的数字，则查找过程结束。
  3. 如果该数字小于要查找的数字，则可以排除此行的其他数字
  4. 如果该数字大于要查找的数字，则可以排行此列及后面的每一列
  5. 重复第一步，直到把所有的行和列都排除掉

代码实现: Swift
这里的实现是对 Swift 里的 Array 添加了 contains 函数，这个 contains 函数利用泛型限制 Array 里的元素的类型必须是 Array，并且子 Array 里的元素必须是遵循 Comparable 协议

1
extension Array{
2
    func contains<C:Comparable>(element:C) -> Bool where Element == Array<C>  {
3
        let count = self.count
4
        var line = 0
5
        var maxRow:Int?
6
        while line < count && (maxRow == nil || maxRow! >= 0){
7
            let row = maxRow != nil ? Swift.min(maxRow!, self[line].count - 1) : (self[line].count - 1)
8
            let currentElement = self[line][row]
9
            if currentElement == element {
10
                return true
11
            }else if currentElement < element {
12
                line += 1
13
            }else {
14
                if maxRow != nil {
15
                    maxRow! -= 1
16
                }else {
17
                    maxRow = row - 1
18
                }
19
            }
20
        }
21
        return false
22
    }
23
}
24
<!--测试-->
25
let array = [[1,2,8,9,10],[2,4,9,12],[4,7,10,10,13],[6,8,11,15,18,20]]
26
for number in 0..<22 {
27
    print("数组中\(array.contains(element: number) ? "包含" : "不包含")\(number)")
28
}

测试结果
针对 [[1,2,8,9,10],[2,4,9,12],[4,7,10,10,13],[6,8,11,15,18,20]]这个数组，测试了从最小值-1 到最大值+1（0-21）之间的所有数据，显示结果是正确的