题目描述

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

解题思路

---

方法一：Map

1、思路：遍历一次数组，将每个元素和它们出现的次数作为键值对保存在map中，然后再次遍历数组，在map中找出数组中重复出现的数字。

2、代码：

class Solution { public: // Parameters: // numbers: an array of integers // length: the length of array numbers // duplication: (Output) the duplicated number in the array number // Return value: true if the input is valid, and there are some duplications in the array number // otherwise false bool duplicate(int numbers[], int length, int* duplication) { map<int, int> mp; for (int i = 0; i < length; i++) { mp[numbers[i]]++; } bool flag = false; for (int i = 0; i < length; i++) { if (mp[numbers[i]] > 1) { *duplication = numbers[i]; return true; } } return flag; } };

3、复杂度：

时间复杂度：O(n)；

空间复杂度：O(n)。

---

方法二：一个萝卜一个坑

1、思路：方法一没有利用到题目所给条件：在一个长度为n的数组里的所有数字都在0到n-1的范围内，因此若数组中没有重复数字，经过排序后，数组中下标为i的数字即为i。利用这个条件，可以在遍历数组的过程中：

若数组中下标为i的数字为i，即a[i] = i，则i++；若数组中下标为i的数字不为i（假如为j）：数组中下标为j的数字也不为j，则将其与数组中下标为j的数字交换，否则数组中下标为j的坑已经被占了，遇到重复数字，返回结果。

需要注意的是，这个算法不能保证输出的是第一个重复的数字，考虑数组[2 2 5 0 1 5]，数组实际输出为5。

2、代码：

class Solution { public: // Parameters: // numbers: an array of integers // length: the length of array numbers // duplication: (Output) the duplicated number in the array number // Return value: true if the input is valid, and there are some duplications in the array number // otherwise false bool duplicate(int numbers[], int length, int* duplication) { int i; for (i = 0; i < length; i++) { while (i != numbers[i]) { if (numbers[i] != numbers[numbers[i]]) { swap(numbers[i], numbers[numbers[i]]); } else { *duplication = numbers[i]; return true; } } } return false; } };

3、复杂度：

时间复杂度：O(n)；

空间复杂度：O(1)。