# 剑指Offer 03 数组中重复的元素
[GitHub-JZ-03](https://github.com/picturetxl/Leetcode_solution/tree/master/JZ-03)
:large_blue_diamond:哈希表
:large_blue_diamond:重复元
## 问题描述
> 取一个数组内重复的元素

## 解法1: 先排序,后遍历 
+ 执行用时：148 ms, 在所有 C++ 提交中击败了25.38%的用户
+ 内存消耗：23.2 MB, 在所有 C++ 提交中击败了100.00%的用户
> 算法复杂度 `O(n*log(n))`,因为C++的sort是`O(n*log(n))`,后面的遍历时间可忽略
```cpp
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
//1.排序
sort(nums.begin(), nums.end());
//2.遍历找出
for (size_t i = 0; i < nums.size(); i++) {
int j = i + 1;
if(nums[i]==nums[j])
{
return nums[i];
}
}
return -1;
}
};
```

## 解法2 采用set的特性
+ 执行用时：156 ms, 在所有 C++ 提交中击败了21.09%的用户
+ 内存消耗：28.6 MB, 在所有 C++ 提交中击败了100.00%的用户
> 算法复杂度 `O(n)` 只需遍历一遍即可
```cpp
class Solution2 {
public:
int findRepeatNumber(vector<int>& nums) {
//* 遍历放进Set中,利用集合的特性(唯一性)进行解决
//* 如果放不进去,那么就说明该元素重复
set<int> myset;
for (size_t i = 0; i < nums.size(); i++) {
if(!myset.insert(nums[i]).second)
{
return nums[i];
}
}
return -1;
}
};

```

## 解法3 使用unordered_set 更快
+ 执行用时：104 ms, 在所有 C++ 提交中击败了53.17%的用户
+ 内存消耗：28.2 MB, 在所有 C++ 提交中击败了100.00%的用户
> 算法复杂度 `O(n)` 只需遍历一遍即可
```cpp

class Solution3 {
public:
int findRepeatNumber(vector<int>& nums) {
//* 遍历放进Set中,利用集合的特性(唯一性)进行解决
//* 如果放不进去,那么就说明该元素重复
unordered_set<int> myset;
for (size_t i = 0; i < nums.size(); i++) {
if(!myset.insert(nums[i]).second)
{
return nums[i];
}
}
return -1;
}
};

```

## :triangular_flag_on_post: TODO
- [ ] :question: unordered_set 和 set的比较