题目描述

从一个序列中找出重复的数，满足 0 <= x <= n - 1

思路

因为有数的范围是[0, n - 1]，原数组的长度也是n那么可以用原来数组作为记录是否存在某个数的表，每次更新数组使得已经出现过得表满足 nums[x] < 0，每次可以取abs(x)得到原来的数字。只要每次判断nums[x] < 0 就可以知道是否在原来已经重复过。0 需要一个位特殊判断一下。

注意点

1.判断一下数据是否超过范围
2.0要用一个bool特殊判断，因为 - 0 = 0
3.要得到原来的数需要取 abs(x)，因为每次更新是in place

算法1

(用nums作为记录) $O(n)$

时间复杂度

循环两次 O(n)

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        bool z = false;
        for(auto x : nums) {
            if(x < 0 || x >= n) {
                return -1;
            }
        }
        for(int i = 0; i < n; i++) {
            int idx = abs(nums[i]);
            if(nums[idx] < 0) {
                return idx;
            }
            if(z && idx == 0) {
                return 0;
            }
            if(idx == 0) {
                z = true;
            }
            nums[idx] = - nums[idx];
        }
        return -1;
    }
};