头像

batman_rua


访客:25

离线:2天前



func duplicateArrayNum(nums []int) int {
    int n = len(nums)

    if n < 1 {
        return -1
    }

    for _,v := range nums {
        if v < 0 || v >= n {
            return -1
        }
    }

    for i,_ := range nums {

        for i != nums[i] { //只要当前i的值和i不一致,就替换掉,为什么是for而不是if? 因为是换走一个值

            if i == nums[i] {
                return i
            }else {
                idx = nums[i] //
                nums[idx], nums[i] = nums[i], nums[i]
            }
        }
    }

    return -1

}



时间复杂度 O(n)
空间复杂读 O(1)

GO 代码

func duplicateInArray(nums []int) int {
    n := len(nums)
    if n < 1 {
        return -1
    }

    /**
    最优解
    时间复杂度 o(n)
    空间复杂度 o(1)

    利用特性,所有的内容都在0~n-1的范围内,
    **/

    //先循环一遍,这一遍,判断所有的值都不在nums里面,不然有可能会有一种情况:先判断有重复的,直接返回对应重复的值了
    for _,v := range nums {
         if v < 0 || v >= n {
            return -1
        }
    }
    for i,_ := range nums {

        //只要当前的值,不等于当前地址的值,就做替换,替换的时候
        //需要注意:如果替换过去的值里,已经有了一个值,而且这个值目前的值一致,则代表已经存在了一个值了
        for i != nums[i] {
            if nums[i] == nums[nums[i]] { //如果发现,当前地址的值,要替换的位置的值是一样的
                return nums[i]
            }else{
                idx := nums[i] //当前的值
                nums[i], nums[idx] = nums[idx], nums[i]
            }
        }
    }

    return -1

}