数组中重复的数字

---

题目描述

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

解题思路

在数组中找重复数字的方法：一般有全遍历，依次比较数组中是否有重复的数字，但是时间复杂度较大；还有一种是通过HashMap进行判断重复，但空间复杂度又会增加。

此题可以使用一种新的判断重复的方法：

• 将给定的数组中元素a[i]，与对应的下标i相比较；
  • 若相等则遍历下一个元素i+1；
  • 若不相等，则将以此元素a[i]为下标的元素a[a[i]]进行比较；
    • 若相等，则说明有重复数字a[i]；
    • 若不想等，则将两个元素互换位置；并执行以上所有步骤，直到遍历完数组。

代码

class Solution
{
public:
    bool duplicate(int numbers[], int length, int* duplication)
    {
        if (length <= 0 || numbers == NULL)
            return false;
        // 判断数组中元素是否在 0~n-1 中
        for (int j = 0; j < length; j++)
        {
            if (numbers[j] < 0 || numbers[j] > length - 1)
                return false;
        }
        
        for (int i = 0; i < length; i++)
        {
            // 若 i != a[i]
            if (numbers[i] != i)
            {
                // 若 a[i] != a[a[i]] 交换两个元素的位置
                if (numbers[i] != numbers[numbers[i]])
                {
                    int temp = numbers[i];
                    numbers[i] = numbers[numbers[i]];
                    numbers[temp] = temp;
                    // 这步交换可以直接使用 swap()函数；
                }
                else
                {
                    *duplication = numbers[i];
                    return true;
                }
            }
        }
        return false;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_50.html