题目描述

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

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

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

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

样例

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

返回 2 或 3。

算法1

(别的题解) $O(不明)$

看别的题解！

时间复杂度 $O(不明)$

参考文献 无

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        const int n=nums.size(),INF=0x3f3f3f3f;
        bool ans[n];
        memset(ans,false,sizeof(ans));
        int answer=INF;
        for(auto x:nums){
            if(x>=n)return -1;
            if(ans[x]==false)ans[x]=true;
            else answer=x;
        }
        if(answer==INF)return -1;
        return answer;
    }
};

C 代码

int duplicateInArray(int *nums, int numsSize){
    const int INF=0x3f3f3f3f;
    int ans[numsSize];
    memset(ans,0,sizeof(ans));
    int answer=INF;
    for(int i=0;i<numsSize;i++){
        if(nums[i]>=numsSize)return -1;
        if(ans[nums[i]]==0)ans[nums[i]]=1;
        else answer=nums[i];
    }
    if(answer==INF)return -1;
    return answer;
}

Java 代码

class Solution {
    public int duplicateInArray(int[] nums) {
        int len=nums.length;
        if(nums==null||len==0)return -1;
        Set<Integer>set=new HashSet<>();
        for(int i=0;i<len;i++)if(nums[i]<0||nums[i]>len-1)return -1;
        for(int i=0;i<len;i++)
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]])return nums[i];
                int temp=nums[i];
                nums[i]=nums[temp];
                nums[temp]=temp;
            }
        return -1;
    }
}

Python 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        if len(nums)==0:
            return -1
        nums.sort()
        for i in range(len(nums)):
            if nums[i]>=len(nums):
                return -1
        for i in range(1,len(nums)):
            if nums[i-1]==nums[i]:
                return nums[i]
        return -1

Javascript 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var duplicateInArray = function(nums) {
    const n=nums.length,INF=0x3f3f3f3f;
    var ans=new Array(n);
    for(var i=0;i<n;i++)ans[i]=false;
    var answer=INF;
    for(var i=0;i<n;i++){
        if(nums[i]>=n)return -1;
        if(ans[nums[i]]==false)ans[nums[i]]=true;
        else answer=nums[i];
    }
    if(answer==INF)return -1;
    return answer;
};

Python3 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        if len(nums)==0:
            return -1
        nums.sort()
        for i in range(len(nums)):
            if nums[i]>=len(nums):
                return -1
        for i in range(1,len(nums)):
            if nums[i-1]==nums[i]:
                return nums[i]
        return -1

Go 代码

func duplicateInArray(nums []int) int {
    if nums==nil{
        return -1
    }
    for _,v:=range nums{
        if v>=len(nums)||v<0{
            return -1
        }
    }
    for i,_:=range nums{
        for nums[i]!=i{
            if nums[i]==nums[nums[i]]{
                return nums[i]
            }else{
                idx:=nums[i]
                nums[i],nums[idx]=nums[idx],nums[i]
            }
        }
    }
    return -1
}