使用内存效率高的方法查找数组中的重复项

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] 范围内，是否所有项目都是无符号的，或者我可以根据需要使用负数吗？ -等。

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

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

Answer 2

注意：如果存在值为零的元素，则解决方案将失败。Olivier的解决方案可以处理这种情况。

使元素的索引为 A[i] 负。它只通过一次循环。

for(int i=0; i<A.Length; i++)
{
if (A[Math.Abs(A[i])] < 0){ return Math.Abs(A[i]);}
A[Math.Abs(A[i])] = -A[Math.Abs(A[i])];
}

Answer 3

我想完善@AryanFirouzian的解决方案并使用yield return返回所有重复项。此外，使用 temp 变量可以简化代码。

public static IEnumerable<int> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int absAi = Math.Abs(A[i]);
if (A[absAi] < 0) {
yield return absAi;
} else {
A[absAi] *= -1;
}
}
}

但是，此解决方案不会返回具有较低索引的元素，如果有多个相同的副本，那么它将多次返回相同的值。另一个问题是 0 不能设为负数。

更好的解决方案可以消除重复的结果，但仍返回第二个索引，并且存在 0 值的问题。它还返回索引本身以演示错误的索引问题

public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int x = A[i] % A.Length;
if (A[x] / A.Length == 1) {
yield return (i, x);
}
A[x] += A.Length;
}
}

测试

var A = new int[] { 3, 4, 2, 5, 2, 3, 3 };
foreach (var item in FindDuplicates(A)) {
Console.WriteLine($"[{item.index}] = {item.value}");
}

它返回

[4] = 2
[5] = 3

我的最终解决方案消除了所有这些问题(至少我希望如此(：它通过向值的第一次出现添加(i + 1) * A.Length来对第一个索引本身进行编码。(i + 1)因为i可以0.然后可以使用反向操作(A[x] / A.Length) - 1对索引进行解码。

然后，由于我们只想在第一个重复值上返回结果，因此我们将该值设置为负值以将其排除在进一步处理之外。随后，可以使用Math.Abs(A[i]) % A.Length检索原始值。

public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
for (int i = 0; i < A.Length; i++) {
int x = Math.Abs(A[i]) % A.Length;
if (A[x] >= 0) {
if (A[x] < A.Length) { // First occurrence.
A[x] += (i + 1) * A.Length; // Encode the first index.
} else { // Second occurrence.
int firstIndex = (A[x] / A.Length) - 1; // Decode the first index.
yield return (firstIndex, x);
// Mark the value as handeled by making it negative;
A[x] *= -1; // A[x] is always >= A.Length, so no zero problem.
}
}
}
}

返回预期结果

[2] = 2
[0] = 3

我们的元素是没有标识的整数。 也就是说，我们可以在任何索引处返回一个重复项，因为无法区分两个相等的整数。如果元素具有标识(它们可以是具有相等值但不同引用的引用类型，或者具有不涉及相等性测试的其他字段(，我们将不得不返回第一次出现

yield return (firstIndex, Math.Abs(A[firstIndex]) % A.Length);

以满足所有要求。

Answer 4

对于想要实现问题的人，我建议使用两种变体(在 c# 中如标签中(，一种使用接受的答案，另一种使用另一个答案的 aproach，使用元素的相反。但是，最后一个解决方案的值为零有问题，需要一些技巧。

第一个解决方案

using System;
public class Program
{
public static void Main()
{
int[] a = {3, 4, 0, 5, 2, 3};
int N = 6;
int min_index = 0; 
bool found = false;
int index = -1;
int i = 0;
while(i < N && !found)
{
if(a[i] >= N) 
index = a[i] % N;
else
index = a[i];
if(a[index] >= N) //its a duplicated elements 
{
min_index = i;
found = true;
}else
{
a[index] += N;
}
i++;
}
Console.WriteLine("Result = " + a[min_index] % N);
}
}

第二种解决方案

using System;
public class Program
{
public static void Main()
{
int[] a = {3, 4, 2, 5, 2, 3};
int N = 6;
int min_index = N-1; 
bool found = false;
int index = -1;
int i = 0;
while(i < N && !found)
{
if(a[i] == -N+1) //it was 0
index = 0;
else
index = Math.Abs(a[i]);
if(a[index] < 0 || a[index] == -N+1) //its a duplicated elements 
{
min_index = i;
found = true;
}else
{
if(a[index] > 0)
{
a[index] = -a[index];
}else
{
a[index] += -N+1;
}
}
i++;
}
if(a[min_index] == -N+1)
a[min_index] = 0;
Console.WriteLine("Result = " + Math.Abs(a[min_index]));
}
}