剑指刷题笔记三：数组中重复数字

• 题目：在一个长度为n的数组力的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道是哪几个数字重复了，也不知道重复了几次。请找出数组中任意一个重复的数字。例如，如果输入的长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字2或者3。
• 思路：其实思路有很多种，但是每种算法的取舍不同，有的空间复杂度更低，有的时间复杂度更低，有的只需要判断，而有的则需要找出实例，有的甚至需要找出所有的实例。一下从几个角度分别进行分析。

①最低时间复杂度：这里主要考虑时间复杂度。利用哈希表，时间复杂度为O（n）。
我们先定义一个计数的数组，然后从前往后扫描原数组，然后在数组所对应的位置元素上++。这样得到一个计数的数组。
如图：
运行程序后，输出了0~n各元素出现的频次。
找到频次大于1的（即：重复的数字）。

实现代码如下：

#include<iostream>
using namespace std;
int main() {
	int test[] = { 2,3,1,0,2,5,3 };
	int mirror[sizeof(test) / sizeof(int)];
	for (int i = 0; i < sizeof(test) / sizeof(int); i++) {
		mirror[i] = 0;
	}
	for (int i = 0; i < sizeof(test) / sizeof(int); i++) {
		mirror[test[i]]++;
	}
	for (int i = 0; i < sizeof(test) / sizeof(int); i++) {
		cout << mirror[i] << " ";
	}
	cout << endl;
	for (int i = 0; i < sizeof(test)/sizeof(int); i++) {
		if (mirror[i] > 1) {
			cout << i << " is repeated. And all repeat " << mirror[i] << " times." << endl;
		}
	}
}

此种算法是既可以找到所有的重复数字，还可以找到具体的重复次数。失去的就是O（n）大小的空间。

②最低空间复杂度：首先排序，将数组排序是一件很容易的事情。然后从排序好的有序数组中，找到重复的数字就会很容易，从前向后扫描就可以了。这里主要考虑空间效率问题。排序一个长度为n的数组需要O(nlogn)的时间。

#include<cstdio>
int main() {
    int test[] = { 2,3,1,0,2,5,3 };//待测试的数组
    int length = sizeof(test) >> 2;
    if (test == nullptr || length <= 0)
        return false;

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

    for (int i = 0; i < length; ++i)
    {
        while (test[i] != i)
        {
            if (test[i] == test[test[i]])
            {
                printf("find repeated number %d", test[i]);
                return 0;
            }

            // 交换test[i]和test[test[i]]             
            int temp = test[i];
            test[i] = test[temp];
            test[temp] = temp;
        }
    }
    printf("don't have repeated number ");
    return 0;
}

运行结果如下：

这种算法只进行判断是否具有重复数字。没有辅助数组，空间复杂度低。
并且由于只需要判断，不需要找到所有的重复数字。所以相比于冒泡排序等排序方法，时间也会很节约。

③不修改数组找出重复数字。

方法一：利用辅助数组，创建辅助数组，和方法一类似。如果数组中被复制的数字是m，则把它复制到辅助数组下标为m的位置。但是，依旧不需要完全进行完全。因为我们只需要找到一个个例就可以。这种算法牺牲了空间。

方法二：采用二分查找。该种算法相比于上面的方法一，可以避免使用O（n）的辅助空间。
我们把从n-1的数字从中间数字m分为两部分。一部分为0~ m，另一部分为m+1~ n-1.如果0~ m的数字数目超过m+1，那么这一半的区间里一定包含重复的数字。否则另一半0~ m必然包含重复数字。我们可以继续把包含重复数字的区间一分为二，直到找到下一个重复数字。

// 参数:
//        test:     一个整数数组
//        length:      数组的长度
// 返回值:             
//        0  - 输入有效
//        -1  - 输入无效
#include<cstdio>
int countRange(const int* numbers, int length, int start, int end)
{
    if (numbers == nullptr)//判断输入是否有效
        return -1;

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

int main() {
    int test[] = { 2,3,1,0,2,5,3 };//待测试的数组
    int length = sizeof(test) >> 2;//相当于除以4，移位运算符效率更高
    if (test == nullptr || length <= 0)//判断test是否有效
        return -1;

    int start = 0;
    int end = length - 1;
    while (end >= start)
    {
        int middle = (end + start) >> 1;//相当于除以2，移位运算符效率更高
        int count = countRange(test, length, start, middle);
        if (end == start)
        {
            if (count > 1) {
                printf("find repeated number is %d", start);
                return 0;
            }
                
            else
                break;
        }

        if (count > (middle - start + 1))
            end = middle;
        else
            start = middle + 1;
    }
    printf("dong't have reapeated number");
    return 0;
}

运行结果：

此算法通过二分法找到是否有重复的数字，且只能找到一个实例。但是优点在于空间复杂读低。不需要辅助数组就可以判断。

• 总结：假期在家刷起了剑指，剑指是众所周知的一本业界面试的非常有名气的书籍。既然针对的是面试，那么就要符合业界的需求。满足不同面试官提出的要求，包括功能要求（找出任意一个重复数字、找出所有重复数字）或者性能要求（时间效率优先、空间效率优先），不同的需求会导致我们最终选取的算法叶不同。而以上较为全面地记录、总结了几种对应不同需求的算法。
  到这里，感觉到面试真的是有难度的，不仅要能解决，还要考虑到问题解决的是否完美，时间、空间复杂度是否符合需求，边界条件，有效输入等等。自己刚刚入门数据结构与算法就从剑指开始，感觉是不是选择的有些门槛过高了呢？着实不知这是不是一条好的途径了。在此，小白一枚希望各位大神多多指教，提出宝贵的学习建议，一起交流。万分感谢！！！