用内存高效的方法在数组中查找重复

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)。

这种方法背后的关键概念是哈希集是这样工作的。从概念上讲，这与鸽子洞原理有着间接的联系。principle

注意:在面试期间，重要的是问一些具体的实现问题，讨论限制，假设等：-列表中项目的数据类型是什么？-如果值在0..A长度-1范围内，所有项目都是没有符号的，或者我可以使用负数(如果我想要的话)等等。

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

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

Answer 2

注意:如果存在值为零的元素，则解决方案将失败。奥利维尔的解决方案可以处理这样的案件。

用Ai阴性指数制作元素。它只循环一次。

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

我们的元素是没有身份的ints。也就是说，我们可以在任何索引处返回一个重复项，因为不能区分两个相同的ints。如果元素具有标识(它们可以是具有相同值但不同引用的引用类型，或者具有其他字段而不涉及等式测试)，那么我们必须返回第一个匹配项

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

以满足所有的要求。