5

这是我不久前遇到的一个有趣的问题，但在解决它时遇到了一些麻烦。

有一个大小为N的未排序整数数组存储有数字1,2..,N+M ，其中缺少M个整数。M和N是事先已知的。编写一个算法以最有效的方式找到丢失的M个整数。

曾尝试将其映射到大小为N + M的数组，以便第i个索引包含值为i的元素，但这需要 2 次扫描（1 次用于映射，1 次用于查找M缺失的数字）。

我遇到的这本书提到了一个单一的扫描解决方案是可能的，但我无法达到它。关于如何解决这个问题的任何想法？

4

1 回答 1

1

您可以使用映射在数组顶部的双向链表来做到这一点。

position 1 2 3 4 5 6 ...
next     2 3 4 5 6 7 ...
prev     0 1 2 3 4 5 ...

在通过输入时，您索引到与每个输入数字对应的位置并更新链表以从链表中删除（跳过）该位置。在输入结束时，链表将仅包含未访问的位置。

于 2012-11-09T03:40:11.043 回答