如题所述
第1个回答 2022-06-17
解析：在这道题的背景下，如果把数字放到他的下标对应的位置，也就是把一个数组还原成一个递增数列，只不过每一个下标对应的数字就是下标本身的话，如果这个数组里面没有重复数字，那么还原可以完美的完成。但是由于数组内有重复数字，那么在还原的过程中，就会发现当需要把它放在合适的位置的时候，这个位置上已经有一个相同的数字了。例如 {0,1,2,2,4,5,6}，下标为 3 的 2 应该放在下标为 2 的位置上，但是这个地方已经有一个 2 了。遇到这种情况，我们就立即可以返回这个数字。
使用这个思路，我们就可以写出算法了。只要当前位置上的数字和下标不相等，那就看看这个数字应该去的地方有没有同样的数字。如果发现那个地方的数字和下标是相同的，那就说明这个地方的数字是重复的，就可以返回了。如果那边的也不对的话，就把当前位置上的数字放到它应该的位置，把那个位置上的数字交换过来。然后继续比较当前位置上的数字和下标，直到当前位置上的数字和下标相等。接着对下一个位置进行同样的处理。如果每一位都是合适的，那就说明这个数组没有重复数字。
上面的算法是没有问题的，但是你可能有疑问：如果这个位置永远都换不来那个合适的数字呢？例如，{1,3,2,4,3} 没有 0 这个数字，那么怎么办呢？答案是不影响。检查第 0 位的时候，会把第 0 位的 1 和第 1 位的 3 互换。这个时候第 1 位就是 1，没毛病。接着会把第 0 位的 3 和第 3 位的 4 互换，这个时候第 3 位也是 3，没毛病。接着会把第 0 位的 4 和第 4 位的 3 互换，发现第 3 位已经是 3 了，此时返回 3。看到没有？即便换不到该有的数字，在交换的过程中也是可以找到重复的数字的。
答案：
解析：上面的那个算法会修改原有的数组。如果要求不修改原有数组，也不能使用 O(n) 的空间来复制一份，可以牺牲一点时间复杂度，那就用下面这个算法。
首先我们考虑一个事实：如果统计数组里面的数字，在区间 [1,N] 的范围内如果出现超过了N个数，那就说明一定至少有一个数字重复了。就像一年有 365 天 (不考虑平闰年)，那么 366 个人中一定至少有两个人的生日重复了。
我们可以使用这个方法来二分的统计数字的出现个数。题目说所有的数字都在 [1,N] 的范围内，那么我就统计 [1,N/2] 和 [N/2+1,N] 的数字出现次数，哪一个次数超过 N/2，哪一个就一定有重复的数字。接下来在重复的那个区间内继续二分统计，直到区间退化为一个数字，而且这个数字出现的次数大于1，那么就找到了这个数字。每统计一次出现次数会占用 O(N) 的时间。二分的统计最多有 log(N) 次统计。所以时间复杂度为 O(NlogN)。
举个例子。{1,2,3,3,4,5,6,7}，长度为 8，每个数字都在 [1,7] 的范围内。先统计 [1,3] 的，有四次，[4,7] 的，也有四次。那么继续统计 [1,3]。1 出现了一次，[2,3] 出现了三次。继续统计 [2,3]。2 出现了一次，3 出现了两次，BOOM，返回 3。
答案：
使用这个思路，我们就可以写出算法了。只要当前位置上的数字和下标不相等，那就看看这个数字应该去的地方有没有同样的数字。如果发现那个地方的数字和下标是相同的，那就说明这个地方的数字是重复的，就可以返回了。如果那边的也不对的话，就把当前位置上的数字放到它应该的位置，把那个位置上的数字交换过来。然后继续比较当前位置上的数字和下标，直到当前位置上的数字和下标相等。接着对下一个位置进行同样的处理。如果每一位都是合适的，那就说明这个数组没有重复数字。
上面的算法是没有问题的，但是你可能有疑问：如果这个位置永远都换不来那个合适的数字呢？例如，{1,3,2,4,3} 没有 0 这个数字，那么怎么办呢？答案是不影响。检查第 0 位的时候，会把第 0 位的 1 和第 1 位的 3 互换。这个时候第 1 位就是 1，没毛病。接着会把第 0 位的 3 和第 3 位的 4 互换，这个时候第 3 位也是 3，没毛病。接着会把第 0 位的 4 和第 4 位的 3 互换，发现第 3 位已经是 3 了，此时返回 3。看到没有？即便换不到该有的数字，在交换的过程中也是可以找到重复的数字的。
答案：
解析：上面的那个算法会修改原有的数组。如果要求不修改原有数组，也不能使用 O(n) 的空间来复制一份，可以牺牲一点时间复杂度，那就用下面这个算法。
首先我们考虑一个事实：如果统计数组里面的数字，在区间 [1,N] 的范围内如果出现超过了N个数，那就说明一定至少有一个数字重复了。就像一年有 365 天 (不考虑平闰年)，那么 366 个人中一定至少有两个人的生日重复了。
我们可以使用这个方法来二分的统计数字的出现个数。题目说所有的数字都在 [1,N] 的范围内，那么我就统计 [1,N/2] 和 [N/2+1,N] 的数字出现次数，哪一个次数超过 N/2，哪一个就一定有重复的数字。接下来在重复的那个区间内继续二分统计，直到区间退化为一个数字，而且这个数字出现的次数大于1，那么就找到了这个数字。每统计一次出现次数会占用 O(N) 的时间。二分的统计最多有 log(N) 次统计。所以时间复杂度为 O(NlogN)。
举个例子。{1,2,3,3,4,5,6,7}，长度为 8，每个数字都在 [1,7] 的范围内。先统计 [1,3] 的，有四次，[4,7] 的，也有四次。那么继续统计 [1,3]。1 出现了一次，[2,3] 出现了三次。继续统计 [2,3]。2 出现了一次，3 出现了两次，BOOM，返回 3。
答案：
