### 题：找出数组中重复的数字。 >`题`：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。  >**题中的第一个测试用例** >**以及需要引入的头文件** >**可以将下面的方法直接放进去测试** ```cpp #include #include #include #include using namespace std; int findRepeatNumber(vector &nums){ size_t slow = 0, fast = 1; while (fast != nums.size()) { if (nums[slow++] == nums[fast++]) return nums[slow]; } return -1; } int main(){ vector nums{ 2, 3, 1 , 0 , 2 , 5 , 3 }; findRepeatNumber(nums); return 0; } ``` # 方法1： **//两个for循环，，最后时间超了** ```cpp //method 1: int findRepeatNumber(vector & nums) { for(int i=0;i & nums) { sort(nums.begin(), nums.end()); vector ::iterator slow = nums.begin(); vector ::iterator fast = slow++; while (fast != nums.end() ) { if (*fast == *slow) cout << *fast; return *slow; fast++; slow++; } return -1; } ``` # 方法3： **sort排序后，利用下标，判断相邻是否相对** ```cpp //method 3: int findRepeatNumber(vector & nums) { sort(nums.begin(), nums.end()); size_t slow = 0, fast = 1; while (fast != nums.size()) { if (nums[slow++] == nums[fast++]) return nums[slow]; } return -1; } ``` # 方法4： **//利用无序map，借用重载的[]赋值操作；pair //value的值进行判断 value 可为bool char等，只要能作为标记即可** ```cpp //method 4: int findRepeatNumber(vector & nums) { std::unordered_map u_map; for(auto e:nums){ if(u_map[e]>0) return e; u_map[e]++; } return -1; } ``` # 方法5： **//通过判断 nums[i] i nums[nums[i]] 的关系** ```cpp //method 5: int findRepeatNumber(vector & nums) { int i = 0; while (i < nums.size()) { if (nums[i] == i) { ++i; continue; } if (nums[i] == nums[nums[i]]) return nums[i]; swap(nums[i], nums[nums[i]]); } return -1; } ```