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

/*
解法1：利用一个哈希表，从头到尾扫描数组中的每一个数字，得出结果。
时间复杂度为O(n),但是最坏情况下要创建一个n-1个大小的哈希表为代价。
*/

#include<iostream>
#include<unordered_map>

using namespace std;

unordered_map<int, int> g_hash_map;

//判断在哈希表中是否有重复的元素
inline bool is_duplicate(const int& num)
{
    if (g_hash_map.find(num) == g_hash_map.end())
    {
        g_hash_map[num] = 1;
        return false;
    }

    return true;
}

int main()
{
    int nums[] = { 2,3,1,0,2,5,3 };   //要查询的数组
    //遍历数组
    for (auto ite = begin(nums); ite != end(nums); ite++)
    {
        if (is_duplicate(*ite))
        {
            cout << "duplicate num = " << *ite << endl;
            break;
        }
    }

    return 0;
}

/*
* 解法二：不需要O(n)的辅助空间，也不需要修改数组。按照二分查找的思想
* 但是时间复杂度为O(nlogn)。
* 我们把1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面为m+1~n。
* 遍历整个数组，统计1~m中元素的数量，如果大于m个，则这个范围内必定有重复的数字。
* 如果没有，则统计数组m+1~n中元素的数量。这样把包含重复数字的区间一分为二，直到找到一个
* 重复的数字。
*/

#include<iostream>
using namespace std;

//统计数组中一定范围内的数字数量
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 getDuplication(const int* numbers, int length)
{
    if (numbers == nullptr || length <= 0)
        return -1;

    int start = 1;
    int end = length - 1;
    while (start <= end)
    {
        int middle = start + ((end - start) >> 1);
        int count = countRange(numbers, length, start, middle);
        if ((end == start) && (count > 1))
        {
            return start;
        }

        if (count > (middle - start + 1))
        {
            end = middle;
        }
        else
        {
            start = middle+1;
        }
    }
    return -1;
}

int main()
{
    int nums[] = { 2,3,5,4,3,2,6,7 };   //要查询的数组

    int result = -1;

    result = getDuplication(nums, sizeof(nums) / sizeof(nums[0]));

    if (result != -1)
    {
        cout << "duplicate number = " << result << endl;
    }
    else
    {
        cout << "Do not have duplicate number." << endl;
    }

    return 0;
}