03.找出数组中重复的数字

一、 题目

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：

[2, 3, 1, 0, 2, 5, 3]

输出：2 或 3

限制：

2 <= n <= 100000

通过次数188,858提交次数280,286

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、 解法

2.1 二分法

二分法 时间 O(log2N) 空间 O(N)

func findRepeatNumber(_ nums: [Int]) -> Int {
    var dic: [Int : Int] = [:]
    var left = 0, right = nums.count - 1
    
    while left <= right {
        if let _ = dic[nums[left]] {
            return nums[left]
        }
        else {
            dic[nums[left]] = 1
        }
        
        if let _ = dic[nums[right]] {
            return nums[right]
        }
        else {
            dic[nums[right]] = 1
        }
        
        left += 1
        right -= 1
    }
    
    return 0
}

2.2 一个萝卜一个坑

由题目限制 n 个元素，取值范围 0～n-1 可知：每个元素的值对应的下标处的元素如果存在相同元素那么就说明重复了。

func findRepeatNumber(in nums: [Int]) -> Int {
    var temp = nums, index = 0
    
    while index < temp.count {
        let currentValue = temp[index]
        
        if currentValue == index {
            index += 1 // 注意前移的条件，不是直接遍历
            continue
        }
        
        if currentValue == temp[currentValue] {
            return currentValue
        }
        
        temp.swapAt(index, currentValue)
    }
    
    return -1
}