2021-11-01:寻找重复数。给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数

2021-11-01:寻找重复数。给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ,找出 这个重复的数 。你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。力扣287。

答案2021-11-01:

方法1:快慢指针。
抽象为环形链表求入环节点。
方法2:位操作。此方法对于1到n都有的情况下适用。1到n,不是都有,不适合。

时间复杂度:O(N)。
额外空间复杂度:O(1)。

代码用golang编写。代码如下:

package main

import "fmt"

func main() {
    if true {
        nums := []int{1, 2, 3, 2, 4, 5, 6}
        ret := findDuplicate(nums)
        fmt.Println(ret)
    }
    if true {
        nums := []int{1, 2, 3, 2, 4, 5, 6}
        ret := findDuplicate2(nums)
        fmt.Println(ret)
    }
}

func findDuplicate(nums []int) int {
    if len(nums) < 2 {
        return -1
    }
    slow := nums[0]
    fast := nums[nums[0]]
    for slow != fast {
        slow = nums[slow]
        fast = nums[nums[fast]]
    }
    fast = 0
    for slow != fast {
        fast = nums[fast]
        slow = nums[slow]
    }
    return slow
}

func findDuplicate2(nums []int) int {
    if len(nums) < 2 {
        return -1
    }
    x1 := 0
    x2 := 0
    for i := 0; i < len(nums); i++ {
        x1 ^= i
        x2 ^= nums[i]
    }
    return x1 ^ x2
}

执行结果如下:
2021-11-01:寻找重复数。给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数


左神java代码

上一篇:Leetcode刷题记录(10):876链表的中间结点


下一篇:LeetCode26 删除有序数组中的重复项