No.0012-CareerCup

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，但是最优解法不是那么容易想到的。个人觉得这道题属于优秀的面试题，无论高手还是菜鸟都有想法，而且一定程度上考验智商。