一个大小为n的数组中缺失了m个整数。

Question

5

我曾经遇到过一个有趣的问题，涉及到IT技术，但是在解决它时遇到了一些困难。

给定一个未排序的整数数组，大小为N，其中存储着数字1,2,...,N+M，有M个整数缺失。已知M和N的值。请编写一种算法以最有效的方式找出这M个缺失的整数。

我尝试将其映射到大小为N+M的数组中，使第i个索引包含具有值i的元素，但这需要两次扫描（一次用于映射，一次用于查找M个缺失的数字）。

我在阅读这本书时发现，它提到了一种单次扫描的解决方案，但我没有能够想到。你有什么关于如何解决这个问题的想法吗？

- sanz

1

你能否写下那个扫描算法？谢谢。 - Summer_More_More_Tea

这个问题似乎非常局限，而且您也没有提供任何证据表明您已经尝试过自己解决这个问题。 - lockstock

@lockstock 很抱歉，我已经编辑了问题。希望这可以帮到你。 - sanz

这是一个常见的面试问题。我相信一旦M足够大，使用O(1)额外内存解决它是不可能的。如果你使用超过O(1)额外内存，那么你很可能不需要扫描那个内存一次。你肯定需要扫描原始数组一次。那就已经两次了。 - Haozhun

2

参见此处的最佳答案：https://dev59.com/dXA75IYBdhLWcg3wDUq2 - Ismail Badawi

@isbadawi 惊人的是，这个链接提供了一个数学解决方案，但作为一个编程解决方案，它有点不可思议。 - A. Webb

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- A. Webb · Accepted Answer

您可以使用在数组上映射的双向链表来实现此操作。

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

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