题目
在一个长度为n的数组里的所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如,如果输入长度为7的数组{2 ,3, 1, 0, 2, 5, 3},那么对应的输出是第一个重复的数字 2。
这个题目在牛客网是请找出数组中第一个重复的数字,书中是“请找出数组中任意一个重复的数字”。如果直接按照书中的代码,那就不能通过牛客网的全部测试用例,这就有点搞了。不过还是先讲一下解题思路吧。
先排序,再扫描
排序后的数组很容易可以找出重复数字,从头到尾扫描一遍,发现相邻两个数相等的情况即找到了重复数字。时间复杂度为 $O(nlogn)$
利用哈希表
从头到尾扫描一遍数组,如果哈希表中没有这个数字,就将它加入哈希表,如果该数字已存在,则找到了重复数字。这个方法可以用 $O(1)$ 的时间来判断哈希表是否包含当前扫描到的数字,整个算法的时间复杂度是 $O(n)$ ,但代价是需要一个 $O(n)$ 大小的哈希表。
利用数组下标
因为数组中所有数字都在0~n-1范围内,如果数组没有重复数字,那么数组排序后里面数字应该与它对应的下标相等。但因为数组中数字有重复,所以某个位置上的数字应该会出现多于一次。其实说的是,某个下标对应着的与下标相等的数字可能出现多次。原书中那句话是,“由于数组中有重复的数字,有些位置可能存在多个数字,同时有些位置可能没有数字。”,当时看到这句话有点懵,难道数组的一个位置还可以挤下两个数字?后来知道他所指的“位置”是指,下标值与数值相等的这种情况。说起位置,就有点想起 PositionalList
…
清楚了上面的情况,那么怎么可以找出重复数字?书中也是一段文字描述,按照里边描述的确可以找出重复数字,但看起来有点不直观,所以画个流程图看看。
阅读更多📰