java-找出去除矩阵中所有 1 所需的最小箭头
发布时间:2022-06-17 03:49:52 286
相关标签: # 移动端
给定一个大小为的二进制矩阵N x M
,我们需要找到移除矩阵中所有1所需的最小箭头数。
可以垂直点击箭头,比如y=6,它将删除matrix[x][6]
哪里0 <= x < N
或者在水平方向上,也就是说在x=5时,它将在matrix[5][y]
哪里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 1
输出:
3
说明:
arrow-1 : x = 1
arrow-2 : y = 2
arrow-3 : y = 3
接近(贪婪):
我们可以计算每个一行和柱然后按降序排列。并从箭头总数中不断减少箭头数,直到箭头数达到<= 0
. 我们能不能停下来,数一数我们做那次手术的次数。
但这种方法的一个问题是,行和列中的箭头可能重叠,因此,一旦我们从行/列中删除所有箭头,并在每次更新时保持数组排序,我们需要某种方法来跟踪行/列中剩余的箭头数。
我们怎样才能正确、最佳地解决这个问题?
特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报