title: 每日一练（1）：找出数组中反复的数字
categories:[剑指offer]
tags:[每日一练]
date: 2022/01/12
每日一练（1）：找出数组中反复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。
示例 1：
输出：
[2, 3, 1, 0, 2, 5, 3]
输入：2 或 3
限度：
2 <= n <= 100000
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
办法一：哈希表
算法流程：
- 初始化： 新建 Hash
- Set ，记为 dicdic ；
- 遍历数组 numsnums 中的每个数字 numnum ：
- 当 numnum 在 dicdic 中，阐明反复，间接返回 numnum ；
- 将 numnum 增加至 dicdic 中；
- 返回 -1−1 。本题中肯定有反复数字，因而这里返回多少都能够。
复杂度剖析：
- 工夫复杂度 O(N)O(N) ： 遍历数组应用 O(N)O(N) ，HashSet 增加与查找元素皆为 O(1)O(1) 。
- 空间复杂度 O(N)O(N) ： HashSet 占用 O(N)O(N) 大小的额定空间。
int findRepeatNumber(vector<int>& num) { unordered_map<int, bool> map; for (int num : nums) { //循环遍历 if (map[num]) { return num; } map[num] = true; } return -1;}办法2：原地替换
算法流程：
1.遍历数组 numsnums ，设索引初始值为 i = 0i=0 :
- 1.若 nums[i] = inums[i]=i ： 阐明此数字已在对应索引地位，无需替换，因而跳过；
- 2.若 nums[nums[i]] = nums[i]nums[nums[i]]=nums[i] ： 代表索引 nums[i]nums[i] 处和索引 ii 处的元素值都为 nums[i]nums[i] ，即找到一组反复值，返回此值 nums[i]nums[i] ；
- 3.否则： 替换索引为 ii 和 nums[i]nums[i] 的元素值，将此数字替换至对应索引地位。
- 2.若遍历结束尚未返回，则返回 -1−1 。
复杂度剖析：
- 工夫复杂度 O(N)O(N) ： 遍历数组应用 O(N)O(N) ，每轮遍历的判断和替换操作应用 O(1)O(1) 。
- 空间复杂度 O(1)O(1) ： 应用常数复杂度的额定空间。
int findRepeatNumber(vector<int>& nums) { int i = 0, temp; while(i < nums.size()) { if(nums[i] == i) { i++; continue; } if(nums[nums[i]] == nums[i]) { return nums[i]; } temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } return -1;}