arrays - n个整数数组中有重复数字，其中元素的范围为n

Question

有一个n个整数的数组，其中元素的范围是n。即，最大数和最小数之差为 n。找出重复的数字。

我无法解决这个问题，实际上无法理解其创建连贯算法的逻辑。有什么建议吗？

Answer 1

给定有n个元素，最大和最小元素之差为n。首先转换数组，使所有元素都在 1 到 n 之间，也就是说，如果初始数组为 {5,5,7,7,9}，则它转换为 {1,1,2,2,5}。

这是通过从每个元素中减去 min-1 来完成的。
所以在上面的例子中我们得到 min = 5，因此 {5-4,5-4,7-4,7-4,9-4} = {1,1,2,2,5}。

现在你可以使用下面的伪代码:

for(i=0;i<n;++i)//line 1
    arr[(arr[i]%(n+1))-1] += n+1;
for(i=0;i<n;++i)//line 3
    cout<<"frequency of "<<i+1<<" is "<<(arr[i]/n+1);

我们正在做的是获取一个元素 arr[i]，并在等于该元素的索引值处添加 n+1(可能是因为元素介于 1 和 n 之间)，例如如果我们有 n = 6 和 element = 2，那么我们在索引“2”处加 7。这是因为稍后除以 n+1，我们得到索引处给定数字的频率。

但是现在出现了一个问题，如果我们更改数组索引处的值，我们必须稍后处理怎么办？

例如我们有一个数组 {5,5,2,2,3}，当我们处理前 5 个时，我们看到数组中的值“3”已被修改。

为了克服这个问题，我们用 (n+1) 执行 arr[i] 的模数(第 2 行)，这样我们就可以取消我们之前在数组中执行的 (n+1) 次加法，因此我们取回数组中存在的原始值。

我们通过将修改后的数组值除以 n+1 来获得每个元素的频率，因为它为我们提供了索引获得 n+1 增量的次数。

这样就可以得到所有元素出现的频率，判断出哪些元素重复了(通过反向映射，数组索引值加上min-1)，也可以回答后面重复元素出现频率的问题问。