找到移除矩阵中所有1的最小箭头。

Question

给定一个大小为N x M的二进制矩阵，我们需要找到所需的最小箭头数来删除矩阵中的所有1。

箭头可以在y= 6处垂直命中，它将在matrix[x][6]中移除所有1's，在0 <= x < N或水平上也可以在x= 5处删除，它将在matrix[5][y]删除所有1，其中0 <= y < M。

我们需要找到箭头的最小数目，需要删除矩阵中的所有1。

样本测试个案:-

输入:

0 0 1 1 0 0
0 1 0 0 1 0
0 0 0 1 0 0
0 0 1 1 0 0

输出:

3

解释:

arrow-1 : x = 1
arrow-2 : y = 2
arrow-3 : y = 3

Approach(Greedy)：

我们可以在每个行、和列上计数1的数目，然后按递减顺序对它们排序。并继续从箭头总数中减少箭头，直到箭头数的计数到达<= 0为止。我们能停下来数一下我们做过那次手术的次数吗？

但是这种方法的一个问题是，行中的箭头和cols可以重叠，因此，一旦我们从行/col中删除所有箭头，并在每次更新发生时保持数组的排序，我们就需要某种方式来跟踪行/列中留下的箭头数。

如何正确、最优地解决 ?

问题？

Answer 1

我认为最低限度可以通过以下方式找到：

计算有行的行数，但这些行只出现在该行中，而不是其他行，也就是说，这是该列中的唯一行，并跟踪这些行发生的唯一列。

在您的示例中，它是x= 1，在本例中有1的列是y= 1，y= 4。

结果是(列总数-在上述行中找到的唯一列数)在您的示例中是:6-2=4。