在Java中查找整数数组中第一个重复的元素

Question

在Java中查找整数数组中第一个重复的元素

23

以下是我遇到的一个常见面试问题，但是我未能以所需的方式改进它。

assume we have an int array int[] A, we want to find the first duplicate entry.

几乎每个人都能考虑使用 HashSet，并在解析过程中添加元素，这将导致 O(n) 的时间复杂度和 O(n) 的空间复杂度。然后我被要求在不使用其他数据结构的情况下解决这个问题。我说最蠢的想法是在 O(n^2) 的时间内比较每个元素。然后我被要求优化 O(n^2) 的时间。
为了改进它，我想到了使用固定大小的数组（假设最大数字为 n），boolean[] b = new boolean[n]。但是我不能使用这种方法。
然后我想到了使用一个 int 变量，并使用位运算。如果最大数小于 32，则对于 n，我们可以将 1 推到 n 位左边并 | 到一个检查器上，然后 & 检查器与数组中的下一个条目进行比较以检查是否 > 0。例如:
```
int c = A[i];
if(check & (1 << c) > 0) return false;
check |= 1 << c;
```

然而这也是不被允许的。

所以有一个提示说我可以使用数组本身作为哈希集/哈希表，并使用“线性哈希”？

有任何帮助吗？谢谢。

- Ruobo Wang

3

"interview-questions"标签描述的前三个单词是“DO NOT USE（请勿使用）”。 - Aaron

1

你认为有可能改进O(n)时间吗？ - esej

2

使用快速排序算法原地对数组进行排序。 - Marko Topolnik

1

对数组进行排序将使得无法识别出第一个重复的条目。 - Marko Topolnik

6

在数组 {1,2,2,1} 中，是数字1还是数字2作为第一个重复项？ - amit

显示剩余10条评论

9个回答

4

我会问面试官为什么不允许您使用“其他数据结构”，而明显有一个专门设计用于此目的的内置结构-HashSet。

1.这是O（n）。您可能无法通过其他方法做得更好，除非您做一些非常聪明的事情并将其降至O（log n）。

2.这是Java-不是C。有现成的数据结构可以轻松完成这项工作，程序员几乎不需要额外付出任何努力。

从Java集合框架文档中：

“集合框架是表示和操作集合的统一体系结构，允许独立于其表示的细节进行操作。它减少了编程工作量，同时提高了性能。它允许不相关API之间的互操作性，在设计和学习新API方面减少了工作量，并促进了软件重用。”

附录

下面的大多数评论认为这只是一种练习-以确定程序员的技能。我对此的反驳很简单：

这个“面试”是针对Java编程职位的。Java是一种面向对象的语言，具有执行此类任务的能力，无需从头设计过程（例如在C和其他低级语言中）。此外，在空间复杂度成为问题时，Java并不是最佳选择。话虽如此，请再次阅读我上面列出的第一项。

- Evan Mulawski

4

我认为在面试问题中限制使用的内容是合理的，以便确定面试者对数据结构的理解。我认为在这种情况下，他们希望他改进空间复杂度，而不是时间复杂度，即在原地完成。 - hatchet - done with SOverflow

@hatchet：我完全同意，但Java是面向对象的，并且具有执行此类任务而无需从头设计过程（如在C中）的能力。此外，如果空间复杂度是一个问题，Java也不是最好的（代码）基础。 - Evan Mulawski

我认为如果面试官直接说“你能给我讲一个时间复杂度为O(n)，空间复杂度为O(1)的解决方案吗？”会更清晰明了。这将明确排除使用外部API数据结构的可能性。 - hatchet - done with SOverflow

@evanMulawski 那么这可能是一个练习，学习如何在没有特定库的情况下完成此操作，了解这些事情的实际工作原理。 - Hawken

@Evan，你永远不必在Java中实现任何空间效率吗？ ;) 在99％的情况下可能不值得付出努力，但将问题重新表述为“提出一个比O（N ^ 2）时间更好且需要O（1）附加内存的解决方案”就可以了。 - Voo

显示剩余2条评论

4

线性哈希作为维基百科所定义的，其优点在于调整大小是逐步进行的，因为桶是以轮换方式逐个拆分的，保持插入时调整大小的恒定平摊时间复杂度。因此，他们的想法是遍历数组，重复使用已经遍历过的元素作为线性哈希的存储。

虽然我远非线性哈希的专家，但我没有看到将哈希表放入数组的任何方法。可以使用n个桶来存储具有线性哈希的n个元素。然而，每个桶中元素的数量是不受限制的，因此需要像链表一样实现每个桶，这会为指针花费额外的O(n)内存。

因此，该算法不会产生比普通的HashSet更好的渐进空间复杂度。但它确实减少了常量因子的内存消耗。

其时间复杂度与普通的HashSet相当。

编辑：我发现这个答案被忽视了（没有投票，没有评论）。它没有用吗？请评论，以便我知道该改进什么。

- meriton

2

我给你点赞，我仔细阅读了它。我也阅读了其他资源，线性哈希是一种相当笨重的结构，根本不适合我们这里如此简约的情况。它有支持结构和一切。我认为面试官真正想表达的是，一种类似哈希的结构逐渐增长的松散意义。 - Marko Topolnik

2

好的，你自己已经给出了答案：线性哈希确实存在。根据http://cgi.di.uoa.gr/~ad/MDE515/e_ds_linearhashing.pdf，它的复杂度为o(1)/o(1)。因此，你可以一次从数组中取出一个元素，并使用前面的几个元素作为哈希映射的内存。
但实际上，这是一种需要自己实现的数据结构。

无论是面试官没有说你必须“不使用其他数据结构”还是面试官实际上没有理解数据结构是什么，都很有可能出现这种情况。

总之，这是一种你要么知道，要么不知道的问题。在面试中想出这个问题是不可能的。我希望你不要为他们工作。

- kritzikratzi

1

+1，这正是我所寻找的答案，我同意你的观点，这是一种“你要么知道要么不知道”的问题，哈哈。 - Ruobo Wang

但您是否有具体的想法，如何在手头的内存限制下实现这一点？在简短地研究了那篇论文之后，对我来说这一点并不明显。 - Marko Topolnik

@Marko Topolnik，我认为这应该是正确的方向，因为面试官问我是否听说过线性哈希，但我仍在努力理解它。 - Ruobo Wang

1

我只是觉得如果这个问题仅仅是一个谷歌查询，而且结果还难以理解，那就有点令人失望了。听起来像是一个有吸引力的问题。 - Marko Topolnik

@Marko Topolnik，好的，我现在不会选择最佳答案，直到我或其他人提供了可接受的线性哈希解决方案。感谢您的解决方案，虽然很好。 - Ruobo Wang

显示剩余5条评论

2

这个算法没有使用线性哈希，但比O(N^2)更快：

1. 选择一个小数C，并使用暴力算法找到数组前C个元素的第一个重复项。如果还没有找到，则清除前C个元素。 2. 保留前N个元素为空，并执行剩余步骤。最初，N=C。每次迭代后，N加倍。 3. 将索引N+1..3*N/2中的数字顺序添加到哈希表中的前N个数组元素中。使用开放地址法。在移动所有N/2个元素后，哈希负载因子应为1/2。清除我们刚刚移动的N/2个元素占用的空间。对于接下来的N/4个元素，在已构建的哈希表中搜索每个元素，然后将它们哈希到始终是元素数量两倍的空间中。继续这样做，直到哈希了N-C个数组元素。在哈希表中搜索其余的C个元素并将它们彼此进行比较。 4. 现在我们有N个数组元素，不包含重复项，占用2*N的空间。在原地重新哈希它们。 5. 依次在这个哈希表中搜索数组的所有其他元素。然后清除这些2*N个元素，将N设置为2*N，并继续执行第3步。

步骤3..5可以简化。只需将索引N+1..3*N/2的元素哈希，并在这个哈希表中搜索数组的所有其他元素。然后对索引3*N/2+1..2*N的元素执行相同的操作。虽然比原始算法慢两倍，但平均时间复杂度仍为O(N log N)。

另一种选择是使用前N个空元素为元素N+1..3*N/2构建二叉搜索树，并在此树中搜索数组的所有其他元素。然后对索引3*N/2+1..2*N的元素执行相同的操作。（仅当数组足够小且其元素可以由整数值索引时才有效）。

上述算法是概率性的，并且平均时间复杂度为O(N log N)。最坏情况下的复杂度为O(N^2)。如果树是自平衡的，则具有二叉搜索树的替代方案可能具有O(N log^2 N)的最坏情况复杂度。但这很复杂。可以使用更简单的算法在O(N log^2 N)的最坏情况下完成任务。

该算法顺序迭代数组并保持以下不变量：可以放置在当前位置左侧、大小为2的幂的最大可能子数组从索引0开始，并已排序；接下来的这样的子数组跟随它并且也已排序；等等。换句话说，当前索引的二进制表示描述了在其之前有多少个已排序的子数组。例如，对于索引87（1010111），我们在索引86处有一个单独元素，在索引84处有一个已排序对，在索引80处有一个大小为4的已排序子数组，在索引64处有一个大小为16的已排序子数组，并且在数组开头有一个大小为64的已排序子数组。

遍历数组
使用二分查找在所有之前的子数组中搜索当前元素。
将当前元素与那些对应于当前索引的二进制表示中尾随"1"的之前子数组一起排序。例如，对于索引87（1010111），我们需要将当前元素与3个子数组（1+1+2+4=8个元素）一起排序。此步骤允许将当前元素添加到子数组中，同时保持算法不变。
继续进行第1步的下一个迭代。

- Evgeny Kluev

做log(n)次遍历数组以保持哈希表中的良好负载因子是个好主意。然而，你的复杂度分析似乎假设在哈希表中进行查找需要常数时间。如果我们使用开放地址法，这是否真的成立？ - meriton

我越了解它，就越明显线性哈希在这里是一个误导。它的唯一好处只在像事务型数据库管理系统这样的情况下，因为每次插入的时间成本都是平衡的，而不是在整个哈希被同时扩展时出现急剧下降。你的一个很好的想法是从暴力方法开始，直到恢复足够的空间以获取有意义的数据结构。渐近性能是最重要的。 - Marko Topolnik

@meriton 哦，我明白了。不仅是它们之间，而且整个数组都要考虑。那么这就是O(CN)的初始命中。 - Marko Topolnik

@meriton：D.Knuth的《计算机程序设计艺术》第3卷第6.4章提供了各种开放寻址算法的大量公式。例如，线性探测（其中最简单的）在搜索失败的情况下需要约0.5 * (1 + 1 / (1 - a)^2)次探测。如果负载因子为0.5，则需要2.5次探测（在搜索成功的情况下甚至更少）。因此，查找需要O(2.5)=O(1)时间。 - Evgeny Kluev

1

这是非常出色的工作，Evgeny。它值得被至少接受三次 :) - Marko Topolnik

显示剩余3条评论

0

我相信这是你的面试官所寻找的“线性哈希”解决方案。我们首先需要假设两个额外的约束条件：

A的长度大于等于A的最大值
A的所有值都是正数

有了这些额外的约束条件，我们可以用更少的时间和空间来解决问题。

好的，让我们看看代码：

int findFirstDuplicateEntry(int[] A) {
    for (int i=0; i<A.length; i++) {
        if (A[Math.abs(A[i])-1]<0)
            return Math.abs(A[i]);
        else {
            A[Math.abs(A[i])-1] = -A[Math.abs(A[i])-1];
        }
    }
    return -1;
}

我在这里做的是使用数组本身来存储一些额外的信息。当我遍历数组时，每次遇到一个值，我将使用该值作为索引。在这个索引处，我将检查该值。如果该值为负数，则我知道我之前已经访问过这里（因为所有值都是正数）。因此，我找到了第一个重复项，并可以退出。否则，我将对该索引处的值取反。

- JackHacks

0

这是一个平均时间复杂度为O(n)的算法

public static int firstRepeatingElement(int[] elements) {
    int index = -1;
    Set<Integer> set = new HashSet<Integer>();

    for (int i = elements.length - 1; i >=0; i--) {
        if (set.contains(elements[i])) {
            index = i;
        }
        set.add(elements[i]);
    }
    if (index != -1) {
        return elements[index];
    }
    throw new IllegalArgumentException("No repeating elements found");
}

这里是测试用例

@Test
public void firstRepeatingElementTest() {
    int [] elements = {1,2,5,7,5,3,10,2};
    int element = ArrayUtils.firstRepeatingElement(elements);
    assertThat(element, is(2));
}

@Test(expected=IllegalArgumentException.class)
public void firstRepeatingElementTestWithException() {
    int [] elements = {1,2,5,7,3,10};
    int element = ArrayUtils.firstRepeatingElement(elements);
    assertThat(element, is(2));
}

- craftsmannadeem

0

我被要求在没有额外内存的情况下，只能使用寄存器。这是我想出来的：

outer: for (i = 0; i < arr.length - 1; i++)
 for (j = i+1; j < arr.length; j++)
   if (arr[i] == arr[j])
     break outer;

如果i和j小于arr.length，则它们是第一个重复值及其匹配项的索引。

由于j从不覆盖arr的整个长度，因此它比O(n^2)略好一些。

- Devon_C_Miller

2

最坏/平均情况仍为O(n^2)，但这是一种不需要额外空间的好解决方案。 - Makoto

我也想到了这个，但是这不是那些人想要的。D: - Ruobo Wang

你可以通过将外部循环中的比较改为 i < arr.length - 1 来降低常数因子，因为当 i == arr.length - 1 时不需要执行任何操作。此外，你的 break 只会跳出内部循环，并且将继续迭代外部循环。 - Brent M. Spell

0

伪代码：

res = -1;
startArray = [...];
sortedArray = mergeSort(startArray);
for i = 1 to n
     x = bynary_search(sortedArray, startArray[i]); //array, element
     if ((sorted_array[x] == sortedArray[x-1])    ||   (sorted_array[x] == sortedArray[x+1]))
           res = i;
           break;
if (res != -1)
     print('First duplicate is ',startArray[res]);
else
     print('There are no duplicates');

归并排序最坏时间复杂度 O(n log n)

二分查找最坏时间复杂度 O(log n)

n 次二分查找最坏时间复杂度 O(n log n)

总共 O(n log n)

- Stefan.Nikolic

特殊情况是当X是第一个（最后一个）元素时，那么sortedArray[x-1]不存在（或者在x是最后一个元素的情况下，sortedArray[x+1]不存在），因此需要进行小的调整。 - Stefan.Nikolic

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marko Topolnik · Accepted Answer

4

我有一个想法：当您沿着数组向下移动时，对已经访问的部分进行排序。通过使用二进制搜索，您可以提高时间效率; 空间为0。排序本身是...插入排序？您基本上按照正常方式运行排序，但是当您搜索要插入新数字的位置时，如果遇到数字本身，则会大声喊出“bingo”。这比零空间+ O(n ²)时间更好。

- Marko Topolnik

这是一个不错的解决方案，但我不认为这是面试官想要的。就像你使用已经检验过的数组部分作为排序分区一样，我认为他们希望将其用作动态哈希表。 - hatchet - done with SOverflow

似乎这个问题的总复杂度不能低于nlog(n)，而任何哈希解决方案都应该能够在O(n)内完成。 - kritzikratzi

5

插入排序的时间复杂度是O(n^2)，这怎么算得上是一种改进呢？ - meriton

@kritzikratzi 我真的怀疑你能否在这种内存限制下实现哈希算法并使其O(1)。还要记住，我们不仅谈论查找，而是查找+插入，每个桶大小为1，因此每次插入都会扩展。 - Marko Topolnik

@marko 我并不是很了解这些，但似乎线性哈希表就是为此而生的。它可以在保持大致恒定的运行时间（不考虑任何内存分配）的同时，每次缩小或扩展一个哈希表元素。 - kritzikratzi