一道小题的不断优化
题目描述：
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
第一次ac
首先先到的是暴力，借鉴桶的概念，使用tmp数组，保存数组下标存在的个数，遍历vector，当tmp[i]>0时，返回 i。
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int size = nums.size();
int a[size+1];
int flag = -1;
memset(a,0,sizeof(a));
for (int i = 0 ;i<size ;++i){
if (a[nums[i]] > 0){
flag = nums[i];
break;
}
a[nums[i]]++;
}
return flag;
}
};
#暴力的想法瞬间的 可优化点还有很多
#160 ms 23.5 MB
第二次ac
由于傻傻遍历，耗时过多，这里我想用vector sort一下，然后遍历，试一下时间上是否有优化。
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int size = nums.size();
int a[size+1];
int flag = -1;
memset(a,0,sizeof(a));
sort(nums.begin(),nums.end());
for (int i = 0 ;i<size ;++i){
if (a[nums[i]] > 0){
flag = nums[i];
break;
}
a[nums[i]]++;
}
return flag;
}
};
#144 ms 23.5 MB
#有优化效果 但是优化程度不理想
第三次ac
错误的set姿势，使用set来看下是否有优化，思路是存放入set，通过set本身函数。
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int size = nums.size();
set<int> key;
set<int>::iterator iter;
int flag = -1;
for (int i = 0 ;i<size ;++i){
iter = key.find(nums[i]);
if (iter != key.end() ){
flag = nums[i];
break;
}
key.insert(nums[i]);
}
return flag;
}
};
#176 ms 28.6 MB
#内存和时间都增长了 分析原因是set姿势不对 亦或者 set也就这样了
第四次ac
思路回到暴力想法，把int数组换为bool型，已知只需判断int是否大于零 ，所以倒不如用bool值，可以优化内存。
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int size = nums.size();
bool a[size+1];
int flag = -1;
memset(a,false,sizeof(a));
for (int i = 0 ;i<size ;++i){
if (a[nums[i]]){
flag = nums[i];
break;
}
a[nums[i]] = true;
}
return flag;
}
};
#80 ms 23 MB
#可以看到内存优化了0.5mb 但是时间上的优化，对比第一个暴力优化程度更高
#原因 使用直接复制 代替++计算 ，使用判断true false 代替 判断>0的计算
#这时我开始看题解讨论 希望被大神们启发 学习到更多
第五次ac
看到c++区大神有40ms 14.2MB后，内心一句666，大神使用bool数组判重拿到的这么优秀的效率。同样第四次的bool判重却80ms，我提交了一次大神的代码，反馈结果为88 ms 23.2 MB，此时判断，可能是该题发布时间久，测试样例的丰富度和复杂度提升。我继续尝试一下哈希map 120 ms 27.9 MB。
