共有回帖数 0 个
-
前几天贴吧里有人问的面试题，有一道变体题目如下：
某数组A[1..n]含有所有从0到n的整数，但其中有一个整数不在数组中。通过利用一个辅助数组B[0..n]来记录A中出现的整数，很容易在O(n)时间内找出所缺的整数。
但是在这个问题中，我们却不能由一个单一操作来访问A中的一个完整整数，因为A中的元素是以二进制表示的。我们所能用的唯一操作就是“取A的第j位”，这个操作所花时间为常数。
试证明：如果访问数组A中信息的唯一方式是这种单一位操作，仍能在O(n)时间内找出所缺的整数。A之外的任一完整整数仍然可以由一个单一操作来访问。
现在只想到了O(nlgn)复杂度的算法，谁能给些指点
A之外的任一完整整数仍然可以由一个单一操作来访问。
这句话应该是解决问题所在，但是没想到应该怎样去利用这一点
楼主 2016-03-31 14:18 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
