在最近的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
从第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)。我个人更喜欢第一个解决方案。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。