找出数组中重复的数字

题目描述

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

返回其中任意一个重复的数都可以

题目分析

首先确定数组里的数字是在给定范围内，否则返回-1

然后将所有元素从首位元素开始，将其放到对应号数的位置上

反复循环，一直将首位元素换作

含有重复数字

例如
nums =[2,1,4,3,2]

• 判断数字是否在范围内就不作解释，自行遍历每一个元素，判断是否在内即可
  
  交换后nums[2]=2，那么此时的nums[0]=4,所以需要再将此时的num[0]中的值放入指定坑位
  
  重复执行操作
  
  此时num[0]=2，那么可以看到此时2号坑有相同元素2，所以无法交换，此时的nums[0]上的2号不等于当前坑号，则返回当前元素

未包含重复元素

例如
nums =[2,1,4,0,3]

• 判断数字是否在范围内就不作解释，自行遍历每一个元素，判断是否在内即可
  
  
  
  此时首位元素num[0]=0，已经等于自己且等于该坑位，所以进行下一个循环
  
  
  这会儿数组已经遍历完毕，未找到重复数字，则 return -1;

  代码实现

  C++

  class Solution { public: int duplicateInArray(vector<int>& nums) { //首先判断是否在n-1范围内 int l=nums.size();//获取输出的长度 for(auto n:nums) if(n<0||n>=l) return -1; //从首位遍历数组 for(int i=0;i<l;i++){ while(nums[nums[i]]!=nums[i]) //如果元素不在对应的坑上，则交换到对应坑位 swap(nums[i],nums[nums[i]]); //交换 if(nums[i]!=i) //判断重复元素 return nums[i]; } return -1; } };

  C

int duplicateInArray(int *nums, int numsSize){
    int i;
    for(i=0;i<numsSize;i++){
        if(nums[i]<0||nums[i]>=numsSize)
            return -1;
    }
    for(i=0;i<numsSize;i++){
        while(nums[nums[i]]!=nums[i]){
            int temp=nums[nums[i]];
            nums[nums[i]]=nums[i];
            nums[i]=temp;
        }
        if(nums[i]!=i)
            return nums[i];
    }
    return -1;
}

运行结果

超出范围

输入
[1, 3, 2, 4, 3, 3, 6, 9]

输出
-1

重复元素

输入
[5, 3, 5, 4, 3, 2, 6, 7]

输出
5

未重复元素

输入
[1, 4, 2, 0, 3, 5, 6, 7]

输出
-1

总结

判断是否存在重复数字，首先得判断数字范围是否在题目规定范围内。其次再把每一个数的循环遍历，放在对应的坑位，如果放不了，就说明这个坑位有相同的数字占用着，那么就可以找到重复的数字