# 面试题 03

找出数组中重复的数字。

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

```
示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
```

限制：

* 2 <= n <= 100000

## Solutions

1. **in-place hash map O(n) S(1)**
2. Since `n` are within the range of `0 - n - 1`, each bucket contains only one item except for numbers occurred more than once.

```cpp
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++)
            // find the right one for this position
            while (i != nums[i]) {
                // find duplicate
                if (nums[nums[i]] == nums[i])
                    return nums[i];
                // put the number in this position into the right position
                swap(nums[i], nums[nums[i]]);
            }

        return 0;
    }
};
```


---

# 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://zhongquan789.gitbook.io/leetcode/lcof/mian-shi-ti-03.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.