杨氏矩阵的查找(复杂度<O(N))
题目:
解释:时间复杂度小于O(N)即不要一个一个的去遍历查找。
思路:
一个3×3的二维数组如图所示:
一:先找到一个最关键的数字,3(下标为0,2)
关键数的关键之处在于(处于最开始一行,也处于最后一列)
如果n>它,代表最开始一行已经不用查找了(因为它是第一行里面最大的)
如果n<它,代表最后一列也不用找了(因为它是第三列(最后一列)里面最小的)
二:被查找的数(n)与关键数进行比较
情况1:n>关键数,最开始一行不用找了,行+1
情况2:n<关键数,最后一列不用找了,列-1
经过对行和列的不断变换,最终会找到n。
代码展示: