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

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)

这种方法背后的关键概念是hashsets以这种方式工作.从概念上讲,这与鸽子原理间接相关. 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])];
    }