# 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
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/03.-zhao-chu-shu-zu-zhong-zhong-fu-de-shu-zi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.