题目：数组中重复的数字

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

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的。但不知道有几个数字重复了，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

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

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

解析

解析题目一

数组在空间上连续且含有下标，此题考虑查找效率
稍加思索，决定利用下标：若数值与下标不同则与数值对应下标的数值进行置换，若置换中发现两数相同则查找结束，如此时间复杂度仅O(n)，代码如下

bool findDuplicate(int arr[], int length, int *duplication)
{
    int temp;
    for (int i = 0; i < length; ++i)
        if (i != arr[i])
            if (arr[i] != arr[arr[i]])
            {
                temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                *duplication = arr[i];
                return true;
            }
    return false;
}

对照书本发现思路相同，nice !😎
原来无意中已利用下标充当Hash Table(哈希表)的思想解决了问题
不过本人漏掉重要的空值检测、边界检测😭，修复代码

bool findDuplicate(int arr[], int length, int *duplication)
{
    if (arr == nullptr || length <= 0)
        return false;
    for (int i = 0; i < length; ++i)
        if (arr[i] >= length || arr[i] < 0)
            return false;
    int temp;
    for (int i = 0; i < length; ++i)
        if (i != arr[i])
            if (arr[i] != arr[arr[i]])
            {
                temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                *duplication = arr[i];
                return true;
            }
    return false;
}

原本以为完美无瑕，测试数组{0,2,0}发现无法找出重复数字。
究其原因对于替换数值后的数组{0,0,2}未再次判断，导致第二位 0 成为漏网之鱼，下为书中神级代码

bool duplicate(int numbers[], int length, int *duplication)
{
    if (numbers == nullptr || length <= 0)
        return false;
    for (int i = 0; i < length; ++i)
        if (numbers[i] >= length || numbers[i] < 0)
            return false;
    int temp;
    for (int i = 0; i < length; ++i)
        // 使用while便无“漏网之0”
        while (i != numbers[i])
        {
            if (numbers[i] != numbers[numbers[i]])
            {
                temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
            }
            else
            {
                *duplication = numbers[i];
                return true;
            }
        }
    return false;
}

解析题目二

禁止修改输入数组？呵！断我财路，emmmm。苦思冥想，仅想到拷贝数组套用题目一方法……

bool findDuplicate(int arr[], int length, int *duplication)
{
    if (nullptr == arr || length <= 0)
        return false;
    for (int i = 0; i < length; ++i)
        if (arr[i] >= length || arr[i] < 1)
            return false;
    int *arrTemp = new int[length - 1];
    for (int i = 0; i < length - 1; ++i)
        arrTemp[i] = -1;
    for (int i = 0; i < length; ++i)
    {
        if (arrTemp[arr[i] - 1] == arr[i])
        {
            *duplication = arr[i];
            return true;
        }
        arrTemp[arr[i] - 1] = arr[i];
    }
    delete arrTemp;
    return false;
}

一筹莫展之下，阅读书中解析顿觉豁然开朗！书中指出，含重复数字范围内数字个数必大于该范围长度。例如

对于长度为3的数组{1,2,2}，范围[1,1]内的数字个数为1等于范围长度1，而范围[2,2]内的数字个数为2大于范围长度1，可以确定重复数字位于范围[2,2]中即为2。
对于长度为5的数组{2,2,3,4,4}，范围[1,2]内的数字个数为2等于范围长度2，而范围[3,4]内的数字个数为3大于范围长度2，可以确定重复数字位于范围[3,4]中。继续分析范围[3,3]内的数字个数为1等于范围长度1，而范围[4,4]内的数字个数为2大于范围长度1，可以确定重复数字位于范围[4,4]中即为4。(此方法对于多个重复数字仅能找到其中之一)

以上两例说明只需对计数范围不断二分法，必定能找出重复数字。因此写出书中神级代码

int countRange(int numbers[], int length, int start, int end)
{
    if (nullptr == numbers)
        return 0;
    int count = 0;
    for (int i = 0; i < length; ++i)
        if (numbers[i] >= start && numbers[i] <= end)
            ++count;
    return count;
}

bool duplicate(int numbers[], int length, int *duplication)
{
    if (nullptr == numbers || length <= 0)
        return false;
    for (int i = 0; i < length; ++i)
        if (numbers[i] >= length || numbers[i] < 1)
            return false;
    int start = 1;
    int end = length - 1;
    while (end >= start)
    {
        int middle = ((end - start) << 1) + start;
        int count = countRange(numbers, length, start, middle);
        if (end == start)
            if (count > 1)
            {
                *duplication = start;
                return true;
            }
            else
                break;
        if (count > (middle - start + 1))
            end = middle;
        else
            start = middle + 1;
    }
    return false;
}

对于此二分查找法，countRange将被调用O(logn)次，而countRange的时间复杂度为O(n)，故总时间复杂度为O(nlogn)。空间复杂度为O(1)，这是利用时间换空间。

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可