[FS] Nikon D90 Box. Free. (Boston)# PhotoGear - 摄影器材
f*s
1 楼
感谢国人大哥给积极反馈
题目如下，一个m,n 矩阵 每一行升序排列，每一列同样升序排列。
要求找到一个数字是否在矩阵中，注意并不保证每一行头元素高于上一行末元素。
1 2 3
2 3 4
3 4 5
简单解 O(min(m,n)*log(max(m,n)))
我后来想的进一步思路，在正对角线上二分都找到i，i+1的线段，从传递性知道 i上面
包括
i的长方形能都小于所求，i+1下面包括i+1都大于所求。譬如找2， 现在正对角线找到
1， 3， 问题转化为在 1 2 ， 2 3 找 最差情况每次排除一半搜索空间。
题目如下，一个m,n 矩阵 每一行升序排列，每一列同样升序排列。
要求找到一个数字是否在矩阵中，注意并不保证每一行头元素高于上一行末元素。
1 2 3
2 3 4
3 4 5
简单解 O(min(m,n)*log(max(m,n)))
我后来想的进一步思路，在正对角线上二分都找到i，i+1的线段，从传递性知道 i上面
包括
i的长方形能都小于所求，i+1下面包括i+1都大于所求。譬如找2， 现在正对角线找到
1， 3， 问题转化为在 1 2 ， 2 3 找 最差情况每次排除一半搜索空间。
