c# - 使用内存高效方法在数组中查找重复项

Question

A是一个整数数组。

所有值都在0之间至 A.Length-1

意思是0 <= A[i] <= A.Length-1

我应该找到重复的元素；如果有多个重复元素，则选择索引较低的元素作为重复项。

例如:

a = [3, 4, 2, 5, 2, 3]

然后

result = 2

这是一道面试题。我使用另一个数组来存储项目并检查它何时重复。然后它让我暂停了一些测试用例。面试官建议只循环数组一次，不要创建任何额外的数据结构。

Answer 1

不需要另一种数据结构。您可以将输入本身用作哈希集。

每次看到一个值时，将 A.Length 添加到与该索引对应的项目。由于值可能已经递增，您应该将值视为 A[i] mod A.length。

如果你发现一个项目已经 >= A.length.. 你有一个重复。 (请记住，问题指出所有项目都在区间 [0, A.Length-1] 中)

跟踪已发现的最低索引。

这导致 O(N) 复杂度(单次通过)并且没有使用额外的数据结构，即大小 O(1)

这种方法背后的关键概念是哈希集以这种方式工作。从概念上讲，这与鸽巢原理间接相关。 https://en.wikipedia.org/wiki/Pigeonhole_principle

注意:在面试过程中，询问具体实现问题、讨论限制、假设等很重要:- 列表中项目的数据类型是什么？- 如果值在 [0..A.length-1] 范围内，所有项目是否都没有符号，或者我可以根据需要使用负数吗？- 等

在面试过程中，我不会声称这是一个完美的答案，相反，我会与面试官讨论假设并相应地进行调整。例如，另一个答案建议使用负数，但项目的数据类型可能是无符号类型等。

面试应该引发技术讨论，以探索您的知识和创造力。