开发者社区> 问答> 正文

在按行排序的矩阵中找到代表最小整数的行

在最近的Java电话采访中,有人问我这个问题:

您将获得具有以下属性的NxN二进制(0-1)矩阵:

每行进行排序(顺序为0,后跟顺序为1) 每行代表一个无符号整数(通过读取位) 每行都是唯一的 例:

0 1 1 1 1 1 0 0 1 每行中的位值被排序,并且行代表整数3、7和1。

查找代表最小整数的行。在上面的示例中,答案是第3行,它表示整数1。

我从二次复杂的蛮力开始。面试官回答说,我没有利用分类财产。

考虑了很多之后,我在每一行上使用了二进制搜索,结果变成了O(nlogn)。他问我是否可以进一步改善。我想了很多,但没有改善。

如果有人可以提出改进建议,我将不胜感激。

另一个例子:

0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 答案将在第3行,该行代表整数0。在最近的Java电话采访中,有人问我这个问题:

您将获得具有以下属性的NxN二进制(0-1)矩阵:

每行进行排序(顺序为0,后跟顺序为1) 每行代表一个无符号整数(通过读取位) 每行都是唯一的 例:

0 1 1 1 1 1 0 0 1 每行中的位值被排序,并且行代表整数3、7和1。

查找代表最小整数的行。在上面的示例中,答案是第3行,它表示整数1。

我从二次复杂的蛮力开始。面试官回答说,我没有利用分类财产。

考虑了很多之后,我在每一行上使用了二进制搜索,结果变成了O(nlogn)。他问我是否可以进一步改善。我想了很多,但没有改善。

如果有人可以提出改进建议,我将不胜感激。

另一个例子:

0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 答案将在第3行,该行代表整数0。 问题来源于stack overflow

展开
收起
保持可爱mmm 2020-02-09 12:16:26 515 0
1 条回答
写回答
取消 提交回答
  • 从第1行开始。继续前进,直到第一个1。然后跳至第2行,但仍留在同一列中,重复右移的过程,直到您点击为止1。重复执行此操作。您上一步右移的行就是您的答案。

    这是一个O(N + M)解(对于NxM矩阵,或者对于正方形NxN矩阵为O(N),如问题所示)。

    使用您的示例:

    0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 该.是在这里代表走过的路径:

    . . 1 1 0 . . . 0 0 0 . . Last right step, therefore this is our answer 1 1 1 1 . 该解决方案适用于非正方形矩阵,对于NxM矩阵保留最坏情况下的O(N + M)效率。

    为什么这样做?保证数字将被排序意味着每行将是一系列0,然后是一系列1。因此,一行的大小等于您在击中1之前可以走的最远距离。因此,如果一行只要跟随0就能使您走得更远,那么它必须比我们之前处理的任何内容都要长。

    Python代码:

    li = [[0, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0], [1, 1, 1, 1]]

    ans, j = 0, 0 for i, row in enumerate(li): while j < len(row) and row[j] == 0: j += 1 ans = i

    print "Row", ans+1, "".join(map(str, li[ans])) 由于始终具有正方形NxN矩阵和不同的行,因此存在一个更简单的解决方案。它们在一起意味着值最低的行将为0 0 ... 0 1或0 0 ... 0 0。这是因为矩阵中代表N + 1个可能的数字中的N个,因此“缺失”数字要么为0(在这种情况下,表示的最小值为1),要么为其他数值(最小值为0)。

    掌握了这些知识之后,我们从右边第二列开始检查是否为0。找到一个时,我们向右看,如果包含另一个0,我们得到答案(只能有一行以a结尾0)。否则,我们将继续在该列中搜索另一个0。如果找不到另一个0,则找到的第一个是我们要查找的行(只能有一个以结尾结尾的行01,因为没有一个结尾为00,这是最小的)。

    Python代码:

    li = [[0, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0], [1, 1, 1, 1]]

    for i, row in enumerate(li): if row[-2] == 0: ans = i if row[-1] == 0: break

    print "Row", ans+1, "".join(map(str, li[ans])) 该解决方案可以最轻松地回答O(N)的问题,但是将其推广到处理非平方NxM矩阵或非唯一数字将使其最坏情况的效率为O(N ^ 2)。我个人更喜欢第一个解决方案。

    2020-02-09 12:16:41
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
重新定义计算的边界 立即下载
低代码开发师(初级)实战教程 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载