这是我前一段时间遇到的一个有趣的问题,并且在解决它时遇到了一些麻烦.
有一个大小为N的未排序整数数组,存储有数字1,2 ..,N + M ,其中缺少M个整数.M和N在手前是已知的.编写算法以最有效的方式找到丢失的M个整数.
尝试将其映射到大小为N + M的数组,以便第i个索引包含值为i的元素,但这需要2次扫描(1次用于映射,1次用于查找M个缺失的数字).
我遇到的这本书提到了单一扫描解决方案是可能的,但我无法达到它.关于如何解决这个问题的任何想法？
您可以使用映射在数组顶部的双向链表来完成此操作。
position 1 2 3 4 5 6 ...
next 2 3 4 5 6 7 ...
prev 0 1 2 3 4 5 ...
在传递输入时，您索引到与每个输入数字相对应的位置，并更新链接列表以从链接列表中删除（跳过）该位置。在输入的末尾，链接列表将仅包含未访问过的位置。
| 归档时间： |
|
| 查看次数： |
197 次 |
| 最近记录： |