Given a matrix with N rows and N columns. Elements in matrix is 1 or 0. Each row and column of matrix is sorted in ascending order. Find the number of 0s in given matrix.
给出一个NxN的方阵，元素只有0或者1，每一行每一列都是升序排列，求矩阵中0的个数。
1. 询问
没什么好问的。
2. 分析
暴力破解
毫无疑问的O(N^2)，但是没有利用行列排序的条件。
改进1
首先假如每一行都是排好序的，可以用二分查找找到第一个1，从而得出1的个数。这样复杂度是O(NlogN)。但是这样没有用到列排序的条件。
改进2
既然行和列都是升序，那么1就在0的右方或者下方，所有1和所有0都是连通的。
因此，可以着重研究0和1的边界。
因为是方阵，有对称性，这里假设从第1列0和1的分界处着手，那么第2列的分界处不可能比它低，因为分界处是0在上1在下，0右边的元素可能是1，那么分界处就变高了，但1的右边的元素不可能是0，因为要升序。也就是说沿着这个分界处往右上走就行了。这样做的复杂度是O(N)。
当然，要考虑全0和全1的情况，特殊处理一下就行。代码里的ind指在01交界处1的行上，假如全0，ind等于n，全1ind等于0。
3. 代码
class Solution:
def countZeros(self, m):
if not m or len(m) == 0:
return 0
n = len(m)
col = res = 0
ind = n
while col < n:
if ind == 0:
col += 1
else:
while ind - 1 >= 0 and m[ind - 1][col] == 1:
ind -= 1
res += ind
col += 1
return res
4. 总结
如果只考虑做出来完事不管最优，难度为Easy，但是最优解法不是那么容易想到的。个人觉得这道题属于优秀的面试题，无论高手还是菜鸟都有想法，而且一定程度上考验智商。
