首页 🍒LeetCode,🐶算法

题目

0.png

思路

1.sort后遍历找到一样的返回。时间复杂O(nlogn)。

2.用哈希表遍历如果这个数字为key的value为0则+1,不为0直接return。时间复杂度O(n),空间复杂度O(n)。

3.时间复杂度O(n),空间复杂度为O(1)的方法:

题目写出数组范围为0~n-1,所以当数组排序之后i的位置的数字应该为i,由于数组中有重复的数字,所以有的位置没有数字,有的位置有多个数字。

从头到尾重新遍历这个数组,当nums[i] != i时,比较nums[nums[i]]位置的值,如果相同则直接return,不同则把两个数交换位置,重复以上过程直到nums[i] == i,或者return。

func findRepeatNumber(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
        if i != nums[i] {
            if nums[i] == nums[nums[i]] {
                return nums[i]
            } else {
                nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
                i--
            }
        }
    }
    return -1
}



文章评论