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;
}