【剑指offer】面试题3:数组中重复的数字【C++版本】

总结的部分题目思路与代码，待完善。

题目一：

找出数组中重复的数字

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

解题思路：

1.把输入的数组进行排序，排序后再判断有无重复数字，时间复杂度为O(n*lgn)，明显这个方法不大好。
2.使用哈希表来解决，时间复杂度为O(n)，但空间复杂度也为O(n)。这个方法尚可接受。
3.第三种方法，把每个数字放回对应位置的方法。如果出现一个数字无法放回（所在位置已经是对应数字了），那么说明该数字重复。

可以AC的解法一：使用hash表【C++版本】

#include <iostream>
#include <vector>
#include <memory>

using namespace std;

bool duplicate(int numbers[], int length, int* duplication);

int main()
{
    int a[] = {2,1,3,1,4};
    int *resu = new int(0);
    duplicate(a, sizeof(a)/sizeof(int), resu);
    cout << *resu << endl;

    //system("pause");
    return 0;
}

bool duplicate(int numbers[], int length, int* duplication) {
    if (numbers == nullptr || length <= 1)return false;

    int *hashTable = new int[length]();
    for (int i = 0; i != length; i++) {
        if (hashTable[numbers[i]]) {
            *duplication = numbers[i];
            return true;
        }
        else {
            hashTable[numbers[i]] = 1;
        }
    }

    return false;
}

可以AC的解法二：交换元素位置【C++版本】

#include <iostream>
#include <vector>
#include <memory>

using namespace std;

bool duplicate(int numbers[], int length, int* duplication);
void swap(int *item1, int *item2);

int main()
{
    int a[] = {2,1,3,1,4};
    int *resu = new int(0);
    duplicate(a, sizeof(a)/sizeof(int), resu);
    cout << *resu << endl;

    system("pause");
    return 0;
}

bool duplicate(int numbers[], int length, int* duplication) {
    if (numbers == nullptr || length <= 1)return false;

    for (int i = 0; i != length; i++) {
        if (numbers[i] == i) {
            continue;
        }

        if (numbers[numbers[i]] != numbers[i]) {
            swap(&numbers[numbers[i]], &numbers[i]);
        }
        else {
            *duplication = numbers[i];
            return true;
        }
    }

    return false;
}

void swap(int *item1, int *item2) {
    int tmp = *item1;
    *item1 = *item2;
    *item2 = tmp;
}

题目二：

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

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

解题思路：

1.这个题目可以依照题目一的思路来，不过由于不能修改输入数组，所以可以构建一个n+1大小的辅助数组，构建了辅助数组之后可以使用hash表也可以使用换位置的思路来做 。
2.使用二分的思想来做，二分基数组。

使用二分思路的解法

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

    int start = 1, end = length - 1;
    while (start < end) {
        int lowCnt = 0;
        int mid = start + ((end - start) >> 1);
        for (int i = 0; i != length; i++) {
            if (numbers[i] <= mid && numbers[i] >= start) {
                lowCnt++;
            }
        }

        if (lowCnt > (mid - start + 1)) {
            end = mid;
        }
        else {
            start = mid + 1;
        }
    }

    return start;
}