面试题3：找到数组中重复的数字

题目1：在一个长度为的数组里，所有数字都在的范围内。数组中某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组的任意一个重复的数字。

解析：在这道题的背景下，如果把数字放到他的下标对应的位置，也就是把一个数组还原成一个递增数列，只不过每一个下标对应的数字就是下标本身的话，如果这个数组里面没有重复数字，那么还原可以完美的完成。但是由于数组内有重复数字，那么在还原的过程中，就会发现当需要把它放在合适的位置的时候，这个位置上已经有一个相同的数字了。例如 {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)，空间复杂度 O(1)
int findDuplicate(int array[], int length)
{
    if (nullptr == array || length <= 0)
        return -1;

    for (int i=0; i<length; ++i)
    {
        if (array[i]<0 || array[i]>length-1)
            return -1;
    }

    for (int i=0; i<length; ++i)
    {
        while (array[i] != i)
        {
            if (array[i] == array[array[i]])
            {
                return array[i];
            }
            else
            {
                int temp = array[i];
                array[i] = array[array[i]];
                array[temp] = temp;
            }
        }
    }

    return -1;
}

题目2：不修改数组的情况下找出重复的数字。在一个长度为的数组里，所有的数字都在的范围内。请找出数组中任意一个重复的数字，但不能修改输入的数组。

解析：上面的那个算法会修改原有的数组。如果要求不修改原有数组，也不能使用 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。

答案：

//时间复杂度为 O(NlogN)，空间复杂度为 O(1)
int count(const int array[], int length, int beg, int end)
{
    if (nullptr==array || length<=0)
        return -1;

    int cnt = 0;
    for (int i=0; i<length; ++i)
    {
        if (array[i]>=beg && array[i]<=end)
            ++cnt;
    }
    return cnt;
}

int findDuplicate(const int array[], int length)
{
    if (nullptr==array || length<=0)
        return -1;
    for (int i=0; i<length; ++i)
    {
        if (array[i]<1 || array[i]>length)
        {
            return -1;
        }
    }

    int beg = 1, end = length-1;
    while (beg<=end)
    {
        int mid = ((end-beg)>>1) + beg;
        int cnt = count(array, length, beg, mid);
        if (beg==end)
        {
            if (cnt>1) return beg;
            else return -1;
        }

        if (cnt>(mid-beg+1)) end = mid;
        else beg = mid+1;
    }

    return -1;
}