检测数组中的重复元素

问题描述

给定一个长度为n的数组，其中每个元素的值都在0到n-1之间。该数组中存在一些重复的数字，但具体的重复次数和哪些数字重复是未知的。请编写一个函数，找出数组中任意一个重复的数字。

例如，输入数组{2, 3, 1, 0, 2, 5, 3}，则输出第一个重复的数字2。

解决方案

解法一：暴力枚举

通过双重循环逐个比较数组中的元素，时间复杂度为O(n^2)。这种方法简单直接，但在处理大数据集时效率较低。

解法二：哈希表实现

利用哈希表（或辅助数组）来记录每个数字出现的次数。遍历数组时，如果某个数字在哈希表中已经存在，则说明找到了重复项。此方法的时间复杂度为O(n)，空间复杂度也为O(n)。

class Solution { public:     bool duplicate(int numbers[], int length, int* duplication) {         if (length <= 0 || numbers == NULL) return false;         // 初始化辅助数组         int* hash = new int[length];         for (int i = 0; i = 2) {                 *duplication = numbers[i];                 return true;             }         }         delete[] hash;         return false;     } };

解法三：原地置换（不使用额外空间）

假设数组的索引与值是一一对应的。遍历数组时，如果当前索引i处的值不等于i，则检查numbers[numbers[i]]是否等于numbers[i]，若相等则找到重复项；否则交换两者的位置，继续检查直到找到重复项。此方法的时间复杂度为O(n)，且不需要额外的空间。

class Solution { public:     bool duplicate(int numbers[], int length, int* duplication) {         if (length <= 0 || numbers == NULL) return false;         // 检查每个元素是否合法         for (int i = 0; i = length) return false;         }         // 原地置换查找重复项         for (int i = 0; i 

参考资料：
【1】NowCoder代码示例
【2】NowCoder题目解析