[数据结构与算法]每日一练-数组中的重复数字

对于此类问题来说,我们可以考虑使用哈希表来进行求解,如果使用哈希表,那么我们可以得到代码如下:

 class Solution {
public:
  int findRepeatNumber(vector<int>& nums) {
  unordered_map<int,int>map;
  for(int i = 0;i<nums.size();++i){
        if(map[nums[i] > 0){
        return map[nums[i]];
}
        map[nums[i]]++;
}
return -1;
}
};

当然,我们还可以考虑进行另外的解法,如果是在原有数组进行修改呢?

题目给出的条件可以看出有n个数字,0----n-1,容器的容量为n

那么可以考虑如下解法:

class Solution {
public:
 int findRepeatNumber(vector<int>& nums) {
 for (int i = 0;i < nums.size(); ++i){
     if (i != nums[i]){
         if (nums[i] != nums[nums[i]]){
                int temp=nums[nums[i]];
                nums[nums[i]]=nums[i];
                nums[i]=temp;
           }
         else
           {
                return nums[i];
           }
       }
   }
    return 0;}
};