目录

• ** 正确代码**

  • 题目分析
  • 具体思路
  • 难点问题
  • 例子

** 正确代码**

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        for(auto x :nums)     if(x<0||x>=nums.size()) return -1;
        for(int i=0;i<nums.size();i++){
            while(nums[i]!=nums[nums[i]]) swap(nums[i],nums[nums[i]]);
            if(nums[i]!=i) return nums[i];
        }
        return -1;
    }
};

题目分析

判断-1的情况

数组中不包含重复数字

数组中数字不到0~1之间

找到重复数字，并返回

具体思路

• 遍历整个数组，若数组存在<0或者>=n的数字，即返回-1；
• 因为数字范围在0n-1，而数组长度在0n-1，将数字与数组下标一一对应，遍历整个数组，若不包含重复数字，即数组下标与数字一一对应，即返回-1；若数组下标不与数字一一对应（nums[i]!=i），即该数字为重复数字。

难点问题

该问题难点在于如何将数组下标一一对应。

笔者初始想法是遍历数组，当nums[i]!=i时，交换（nums[i],nums[nums[i]]）内容，可忽略了一个问题，当数组

存在重复元素时，会陷入死循环。

以上情况会nums[0]永远不会等于0，陷入死循环。

上网搜索之后，发现代码

  while(nums[i]!=nums[nums[i]])
  swap(nums[i],nums[nums[i]]);

它是将nums[i]是指作为数组下标，将nums[nums[i]] 与nums[i]交换

交换后

nums[i]对应。

如何判断是重复数字

这里有一个前提，就是数组下标与数组内容是一一对应的，若存在重复数字，即数组下标与数据内容不一相等，即为重复数字。

例子

• 包含重复数字的例子

将数组下标与数组内容一一对应后

• 不包含重复数字的例子

将数组下标与数组内容一一对应后