剑指offer-在一维数组中找重复出现的数。

描述:

数组大小为n，数字都是0-n-1，找数组中重复出现的数。

思路：

1.用哈希表记录数字是否出现过，需要额外空间。

1. 每个数都在0-n-1间。对数组排序，每个数应该在的下标与它本身的数相同，每个数经历最多两次交换到达应该在的下标。若发现此时位置上有和它一样的数就说明它是重复的。
   不用额外空间。

   代码：

bool FindduplicateInN(int arr[], int len, int& num)
{
    if (arr == NULL || len <= 0)
        return false;
    for (int i = 0; i < len; i++)
    {
        if (arr[i] >= len)
            return false;
    }
    for (int i = 0; i < len; i++)
    {
        
        while (arr[i] != i)
        {
            int j = arr[i];
            if (arr[j] == arr[i])
            {
                num = arr[j];
                return true;
            }
            else
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }
    }
    return false;
}

剑指offer-在一维数组中找重复出现的数。

原文：https://www.cnblogs.com/void-lambda/p/12465174.html