剑指 Offer 03. 数组中重复的数字
解题思路：1.使用hash，空间复杂度为O(n)。2. 原地置换（交换萝卜），空间复杂度O(1)。
代码：
// 1. hash
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_set<int> hashset;
for (int i = 0; i < nums.size(); ++i) {
if (hashset.count(nums[i])) {
return nums[i];
} else {
hashset.insert(nums[i]);
}
}
return -1;
}
};
// 2. 原地置换
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
while (i != nums[i]) {
if (nums[i] == nums[nums[i]]) return nums[i];
int tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
}
return -1;
}
};
