剑指offer - 数组中重复的数字

找出数组中重复的数字

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

思路1:

解决这个问题的一个简单的方法是先把输入的数组排序。从排序的数组中找出重复的数字是一件很容易的事情，只需要从头到尾扫描排序后的数组就可以了。排序一个长度为n的数组需要O(nlogn)的时间

思路2:

还可以利用哈希表来解决这个问题。从头到尾顺序扫描数组的每个数字，每扫描到一个数字时候，都可以用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字，就把它加入哈希表，如果哈希表里已经存在该数字，就找到一个重复的数字。这个算法的时间复杂度是O(n)，但它提高时间效率是以一个大小为O(n)的哈希表为代价的。

思路3:

注意到数组中的数字都在0~n-1的范围内。如果这个数组中没有重复的数字，那么当数组排序之后数字i将出现在下标为i的位置，由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字

现在重排这个数组。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先比较这个数字（用m表示）是不是等于i。如果是，则接着扫描下一个数字；如果不是，则再拿它和第m各数字进行比较。

如果它和第m个数字相等，就找到了一个重复的数字（该数字在下标为i和m的位置都出现了）；如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。

接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字

具体例子分析

以数组{2,3,1,0,2,5,3}为例来分析找到重复数字的步骤。数组的第0个数字（从0开始计数，和数组的下标保持一致）是2，与它的下标不相等，于是把它和下标为2的数字1交换。交换之后的数组是{1,3,2,0,2,5,3}。

此时第0个数字是1，仍然与它的下标不相等，继续把它和下标为1的数字3交换，得到数组{3,1,2,0,2,5,3}。接下来继续交换第0个数字3和第3个数字0，得到数组{0,1,2,3,2,5,3}。

此时第0个数字的数值为0，接着扫描下一个数字。在接下来的几个数字中，下标为1、2、3的3个数分别为1、2、3，它们的下标和数值都相等，因此不需要执行任何操作。

接下来扫描到下标为4的数字2，由于它的数值与它的下标不相等，再比较它和下标为2的数字，注意到此时数组中下标为2的数字也是2，也就是数字2在下标为2和下标为4的两个位置都出现了，因此找到一个重复的数字。

实现如下

//nullptr是C++11语言标准用来表示空指针的常量值，可以指派给任意类型的指针变量
bool duplicate(int numbers[], int length, int *duplication)
{
    if (numbers == nullptr || length == 0) // 数组长度为0
    {
        return false;
    }
    for (int i = 0; i < length; i++) {
        if (numbers[i] < 0 || numbers[i] > length - 1) // 保证输入的内容是有效的，负数和超过最大值的内容存在，即找不到
            return false;
    }
    for (int i = 0; i < length; i++) {
        while (numbers[i] != i) { // 如果对应的值和下标相等，那么继续下一个值的判断
            if (numbers[i] == numbers[numbers[i]]) // 如果当前下标值与对应位置下标的值相等，则找到了重复的数字
            {
                *duplication = numbers[i];
                return true;
            }
            // 不相等，交换位置的值，并重新开始比较
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return  false;
}

上述代码中，找到的重复数字通过参数duplication传给函数的调用者，而函数的返回值表示数组中是否有重复数字。当输入的数组中包含重复数字时，返回true，否则返回false

代码中尽管有一个两重循环，但每个数字最多交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。另外，所有的操作步骤都是在输入数组上进行的，不需要额外的分配空间，因此空间复杂度为O(1)

完整代码

#include <iostream>
using namespace std;

bool duplicate(int numbers[], int length, int *duplication)
{
    if (numbers == nullptr || length == 0) // 数组长度为0
    {
        return false;
    }
    for (int i = 0; i < length; i++) {
        if (numbers[i] < 0 || numbers[i] > length - 1) // 保证输入的内容是有效的，负数和超过最大值的内容存在，即找不到
            return false;
    }
    for (int i = 0; i < length; i++) {
        while (numbers[i] != i) { // 如果对应的值和下标相等，那么继续下一个值的判断
            if (numbers[i] == numbers[numbers[i]]) // 如果当前下标值与对应位置下标的值相等，则找到了重复的数字
            {
                *duplication = numbers[i];
                return true;
            }
            // 不相等，交换位置的值，并重新开始比较
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return  false;
}

// 测试相关代码
// 判断数组中是否包含对应的数字
bool contains(int array[], int length, int number)
{
    for(int i = 0; i < length; ++i)
    {
        if(array[i] == number)
            return true;
    }

    return false;
}

// 测试函数
void test(char* testName, int numbers[], int lengthNumbers, int expected[], int expectedExpected, bool validArgument)
{
    printf("%s begins: ", testName);

    int duplication;
    bool validInput = duplicate(numbers, lengthNumbers, &duplication);

    if(validArgument == validInput)
    {
        if(validArgument) // 参数是有效的
        {
            if(contains(expected, expectedExpected, duplication)) // 是否和预期结果一样
                printf("Passed.\n");
            else
                printf("FAILED.\n");
        }
        else
            printf("Passed.\n");
    }
    else
        printf("FAILED.\n");
}

void test1()
{
    int numbers[] = { 2, 1, 3, 1, 4 };
    int duplications[] = { 1 };
    test("Test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}

void test2()
{
    int numbers[] = { 2, 4, 3, 1, 4 };
    int duplications[] = { 4 };
    test("Test2", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}

void test3()
{
    int numbers[] = { 2, 4, 2, 1, 4 };
    int duplications[] = { 2, 4 };
    test("Test3", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}

void test4()
{
    int numbers[] = { 2, 1, 3, 0, 4 };
    int duplications[] = { -1 }; // not in use in the test function
    test("Test4", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), false);
}

void test5()
{
    int numbers[] = { 2, 1, 3, 5, 4 };
    int duplications[] = { -1 }; // not in use in the test function
    test("Test5", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), false);
}

void test6()
{
    int* numbers = nullptr;
    int duplications[] = { -1 }; // not in use in the test function
    test("Test6", numbers, 0, duplications, sizeof(duplications) / sizeof(int), false);
}

int main(int argc, const char * argv[]) {
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
    return 0;
}

不修改数组找出重复的数字

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

思路1:

这一题看起来和前面题目类似。由于题目要求不能修改输入的数组，我们可以创建一个长度为n+1的辅助数组，然后逐一遍历把原数组的每个数字复制到辅助数组。如果原数组中被复制的数字是m，则把它复制到辅助数组下标为m的位置，这样就很容易发现哪个数字是重复的。由于需要创建 一个数组，该方案需要O(n)的辅助空间

思路2:

尝试避免使用O(n)的辅助空间。为什么数组中会有重复的数字？假如没有重复的数字，那么在1～n的范围内只有n个数字。由于数组里包含超过n个数字，所以一定包含了重复的数字。看起来在某些范围里数字的个数对解决问题很重要

我们把从1～n的数字从中间的数字m分为两部分，前面一半为1～m，后面一半m+1~ n。如果1～m的数字的数目超过m，那么这一半的区间里一定包含重复的数字；否则，另一半m+1~n的区间里一定包含重复的数字。我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法和类似，只是多了一步统计区间里数字的数目

我们以长度为8的数组{2，3，5，4，3，2，6，7}为例分析查找的过程。根据题目要求，这个长度为8的所有数字都在1～7的范围内。中间的数字4把1～7的范围分为两段，一段是1～4，另一段是5～7。接下来统计1～4这4个数字在数组中出现的次数，他们一共出现了5次，因此这4个数字中一定有重复的数字。

接下来我们再把1～4的范围一分为二，一段是1、2两个数字，另一段是3、4两个数字。数字1或2在数组中一共出现过2次，我们再统计数字3、4出现的次数，他们一共出现了3次。这意味这3、4两个数字一定有一个重复了，我们再统计这两个数字在数组中出现的次数。接着发现数字3出现了两次，是一共重复数字。

// 统计个数
int countRange(const int *numbers,int length, int start, int end)
{
    if (numbers == nullptr)
        return 0;
    int count = 0;
    for (int i=0; i<length; i++)
        if (numbers[i]>=start&&numbers[i]<=end)
            ++count;
    return count;
}

int getDumplication(const int* numbers, int length)
{
    if (numbers == nullptr || length <= 0)
        return -1;

    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)
                return start;
            else
                break;
        }
        if (count>(middle-start+1))  
            end = middle;
        else
            start = middle +1;
    }
    return -1;
}

上述代码按照二分查找的思路，如果输入长度为n的数组，那么函数countRange将被调用O(logn)次，每次需要调用O(n)的时间，因此总的时间复杂度是O(nlogn)，控件复杂度为O(1)。和最前面提到的需要O(n)的辅助空间算法相比，这种算法相当于以时间换空间

需要指出的是，这种算法不能保证找出所有重复的数字。例如，该算法不能找出数组{2，3，5，4，3，2，6，7}中重复的数字2，这是因为在1～2的范围里有1和2两个数字，这个范围的数字也出现2次，此时我们用该算法不能缺点是每个数字各出现一次还是某个数字出现两次。

参考

《剑指offer》