剑指Offer面试题3：数组中重复的数字

数组是占据一块连续内容并按照顺序存储数据的数据结构。创建数组需要先指定数组的容量大小，然后根据大小分配内存，因此空间效率不高，经常会有空闲的区域。由于数组中的内存是连续的，可以根据下标在O(1)时间读写任何元素，所以它的时间效率很高。

题目一：找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或3。
LeetCode力扣链接：[https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/]

这道题有两个简单的题解：

将数组排序，然后遍历找出与前一元素相同的数组元素即可。排序需要O(nlogn)的时间复杂度，遍历一遍需要O(n)，所以总的时间复杂度为O(nlogn + n)。
利用哈希表在遍历数组过程中映射数组元素的存在情况：创建一个哈希表，然后遍历原数组，每当出现一个新数字的时候就把它加入到哈希表里。这种算法的时间复杂度为O(n)，但是由于创建了哈希表，所以还有空间复杂度为O(n)。

但是，还有没有不需要创建新的内存空间的算法呢？

思路

我们已知数字都在0~n-1的范围内，这意味着将数字从小到大排序后每个数组元素的下标将会和数字相等。利用这个特性，我们可以准确找出每个数字应该存在的位置，如果在排序过程中发现该位置已经被对应数字占用了，那么我们就可以知道这是重复数字了。由于不能创建新对象，我们在将数字归位的时候只能将其与取出的数字进行位置交换。如此一来，只要完整遍历一次数组就能找出重复数字了。

举例

以题目中的{2, 3, 1, 0, 2, 5, 3}为例，我们从第一个元素开始遍历。第一个元素是nums[0]=2，应该放在nums[2]=1的位置，我们交换两者的位置后使得nums[0]=1，由于nums[0]里的数字不应该为1，我们要继续帮1找位置；我们将num[1]=3和nums[0]=1进行交换，得到nums[0]=3；继续帮3找位置，将nums[0]=3和nums[3]=0找位置，得到nums[0]=0；由于0的位置正确，这时我们就可以看下一个元素，现在的数组是{0, 1, 2, 3, 2, 5, 3}；我们遍历了nums[1]、nums[2]、nums[3]发现数字都是正确的，直到nums[4]=2；我们像之前一样帮2找位置，这时我们又发现nums[2]=2，也即位置被正确数字占用，意味着出现重复数字，于是我们可以跳出遍历返回该重复数字。

原文代码(C/C++)

https://github.com/zhedahht/CodingInterviewChinese2/blob/master/03_01_DuplicationInArray/FindDuplication.cpp

个人编写代码(C#)

public int FindRepeatNumber(int[] nums)
{
    if (nums != null && nums.Length > 1)
    {
        for (int i = 0; i < nums.Length; ++i)
        {
            if (nums[i] < 0 || nums[i] > nums.Length -1)
            {
                return -1;
            }
        }

        for (int i = 0; i < nums.Length; ++i)
        {
            while (nums[i] != i)
            {
                if (nums[i] == nums[nums[i]])
                {
                    return nums[i];
                }

                int temp = nums[i];
                nums[i] = nums[nums[i]];
                nums[temp] = temp;
            }
        }
    }

    return -1;
}

题目二：不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或3。

这题可以用题目一的简单题方法二来做。由于数组可以被看作是一类特殊的哈希表（下标作为键），我们这里还可以创建一个新数组nums2，并且遍历原数组，逐一把遍历到的数字复制到新数组对应下标的位置中，使得nums2[i]=i。其实也可以用新数组记录原数组中数字出现次数。

这道题和前一道题最大的区别就是：题目一中所有可能出现的数字总共为n个和数组长度是一致的，但是这道题明确数字可能性为n种的时候，数组长度是n+1；同时，把数字范围限定从1开始，也更便于后面的算法讲解。；同时，把数字范围限定从1开始，也更便于后面的算法讲解。

如前面所说，这种算法的时间复杂度为O(n)，空间复杂度也为O(n)。有没有既不需要辅助空间也不需要修改数组的算法呢？

思路

已知如果要将n个不同数字放在长度为n+1的数组里，那么至少有一个数字会重复出现一次（鸽巢原理Pigeonhole Principle）。我们可以采用二分法来找到重复数字出现的范围并逐渐缩小这个范围，具体做法是：先将1~n分成两个区间，1~m和m+1~n；然后遍历数组，看出现在1~m范围内的数字个数，如果大于m，那么我们可以认为1~m范围内必有重复数字，反之重复数字出现在m+1~n范围内。

举例

以题目中长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}为例，我们首先将所有可能出现的数字1~7分成两个区间，1~4和5~7，然后遍历数组发现出现在1~4之间的数字有5个，在数组中被标记为加粗字体如下{2, 3, 5, 4, 3, 2, 6, 7}，由于5>4，我们可以认为1~4之间一定存在某个重复数字；我们接着把1~4分成1~2和3~4，遍历发现出现在1~2之间的数字有2个，则重复数字一定出现在另一个区间3~4中；我们最后将3~4分成3和4就能发现3出现了2次，是重复数字。

原文代码(C/C++)

https://github.com/zhedahht/CodingInterviewChinese2/blob/master/03_02_DuplicationInArrayNoEdit/FindDuplicationNoEdit.cpp

个人编写代码(C#)

public int FindRepeatNumber2(int[] nums)
{
    if (nums != null && nums.Length > 1)
    {
        int left = 0;
        int right = nums.Length - 1;
        while(right >= left)
        {
            int mid = (left + right) / 2;
            int acc = 0;
            foreach (int num in nums)
            {
                if (num < 0 || num > nums.Length - 1)
                {
                    return -1;
                }

                if (num <= mid && num >= left)
                {
                    ++acc;
                }
            }

            if (left == right)
            {
                if (acc > 1)
                    return left;
                else
                    return -1;
            }

            if (acc > (mid - left) + 1)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
    }

    return -1;
}

易错易混淆点

这里二分的是可能出现的数字，而非数组。