这题不修改数组找出重复数字，怎么改写为长尾？

本文共计707个文字，预计阅读时间需要3分钟。

题目：在一个长度为n+1的数组中，所有数字都在1到n的范围内，找出数组中任意一个重复的数字。

示例：如果输入为2 3 2 1 4，请输出2。

一、题目

在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字 2 或 3。

输入参数：一个整数数组numbers，数组长度length

输出参数：-1（代表输入参数出错），或者是重复的数字

二、解法

2.1分析1：辅助数组法

由于不能修改输入的数组，我们可以创建一个长度为 n+1的辅助数组，然后逐一将原数组的每个数字复制到辅助数组。如果原数组中被复制的数字是m，则把它复制到辅助数组下标为m的位置。如果下标为m的位置已经有数字了，则说明该数字重复。

该解法的空间复杂度是O（n）。