编程珠玑

如何高效地找出数组中的重复数字

问题描述

给定一个长度为n的数组，其中所有元素的值均在[1,n]之间，现在需要找出数组中的所有重复数字。

解法分析

解法一

这种算法虽然不是排序算法，但它可以在O(n)时间内（顺带用了O(n)的空间）快速地找出数组中重复出现的数字。这个算法的关键在于把相应元素放到与其下标相等的位置上，假如值为m的元素在下标i出现，我们就将其放在下标m处。在这个过程中如果发现下标m处已存在了值为m的元素，那么m就是重复的数字。

代码实现

复杂度分析

时间复杂度：O(n)。由于整个算法只包含一次遍历并可以在常量时间内完成复杂的表格交换，所以这个算法是真正的 O(n) 级别的。

空间复杂度：O(n)。需要额外的空间来存储交换位置后的数组。

优化

虽然第一种解法已经很高效了，但是还可以再提高一些效率。具体来讲，我们还可以考虑将其改为只占用一个额外的常量级别的空间用来寻找那个重复出现的数字。具体来讲，每当算法交换一对下标（m,n）时，我们实际上就把数字m交换到了下标为n的位置上。因此，只要我们每次交换时核对一下交换过来的数字是否和下标相等，我们就能发现有些数字重复了。我们使用两个标志，一个是重复标志duplicate，另一个是超出范围标志outofrange。第一个标志我们可以通过寻找重复的数字来回答问题，而将第二个标志设置为true，可以避免出现数组越界的情况。

代码实现

复杂度分析

时间复杂度：O(n)。由于整个算法只包含一次遍历并可以在常量时间内完成复杂的表格交换，所以这个算法是真正的 O(n) 级别的。

空间复杂度：O(1)。只需要使用两个常量级别的标志即可。