一、题目描述

二、解题思路

这是剑指Offer的原题。。。。。。评论区用的都是有环链表的方法

  • 一个萝呗一个坑儿，如果没有重复那么下标与元素值应该可以达成一一对应
  • 那么如果当前下标和元素值不同，那么我们就不断地调整，也就是说把这个元素调到它应该在的位置
  • 如果发现了它要去的那个地方被一个和它相等的元素占了，那就直接返回
  • over

时间复杂度O(n)，空间复杂度S(1)

三、解题代码

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

四、运行结果

我是真的理解不了为什么空间复杂度为S(1)才击败了百分之五。。。。。。。。