我曾经遇到过一个有趣的问题,涉及到IT技术,但是在解决它时遇到了一些困难。
给定一个未排序的整数数组,大小为N,其中存储着数字1,2,...,N+M,有M个整数缺失。已知M和N的值。请编写一种算法以最有效的方式找出这M个缺失的整数。
我尝试将其映射到大小为N+M的数组中,使第i个索引包含具有值i的元素,但这需要两次扫描(一次用于映射,一次用于查找M个缺失的数字)。
我在阅读这本书时发现,它提到了一种单次扫描的解决方案,但我没有能够想到。你有什么关于如何解决这个问题的想法吗?
我曾经遇到过一个有趣的问题,涉及到IT技术,但是在解决它时遇到了一些困难。
给定一个未排序的整数数组,大小为N,其中存储着数字1,2,...,N+M,有M个整数缺失。已知M和N的值。请编写一种算法以最有效的方式找出这M个缺失的整数。
我尝试将其映射到大小为N+M的数组中,使第i个索引包含具有值i的元素,但这需要两次扫描(一次用于映射,一次用于查找M个缺失的数字)。
我在阅读这本书时发现,它提到了一种单次扫描的解决方案,但我没有能够想到。你有什么关于如何解决这个问题的想法吗?
您可以使用在数组上映射的双向链表来实现此操作。
position 1 2 3 4 5 6 ...
next 2 3 4 5 6 7 ...
prev 0 1 2 3 4 5 ...
O(N) + O(M)
更好,因为在达到 N
的末尾之前,你无法知道 M
中缺失的最后一个元素是什么。如果你已经开始打印了,N
的最后一个元素可能会破坏你的输出,因为它可能包含你已经打印过的内容。当 M<<N 时,从空间复杂度的角度来看,你可能可以做得更好,就像上面评论中链接到的相当令人印象深刻的数学答案所示。 - A. Webb