23

这是我遇到的一个常见面试问题，但是我未能按照要求的方式改进它。

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

  1. 几乎每个人都可以想到使用 HashSet，并在解析时添加。这将导致 O(n) 时间和 O(n) 空间。在此之后，我被要求在没有其他数据结构的情况下解决它。我说最愚蠢的想法是在 O(n^2) 时间内比较每一个。然后我被要求改进 O(n^2) 时间。

  2. 为了改进它，我想到了使用固定大小的数组（假设最大数为 n）， boolean[] b = new boolean[n]; 但是我不允许使用这种方法。

  3. 然后我想到了使用一个 int 变量，使用位操作，如果最大数小于 32，那么对于 n 我们可以向左推 1 到 n 位和 | 到检查器，然后&检查器到数组中的下一个条目以检查它是否> 0。例如：

    int c = A[i];
if(check & (1 << c) > 0) return false;
check |= 1 << c;

但是，这也是不允许的。

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

有什么帮助吗？谢谢

4

9 回答 9

4

我有一个想法：当你沿着数组前进时，你对你访问过的部分进行排序。通过使用二分搜索，您将缩短时间；空间为0。排序本身是......插入排序？您基本上正常运行排序，但是当您搜索插入新数字的位置时，如果您点击数字本身，您会喊“宾果”。这是对零空间 + O(n 2 ) 时间的改进。

于 2012-05-26T15:13:57.407 回答
4

我会问面试官为什么他们不希望你使用“其他数据结构”，因为显然有一个为此目的而设计的内置结构 - HashSet。

  1. 它开着）。使用其他方法你可能不会做得比这更好，除非你做了一些非常聪明的事情并将其降低到 O(log n)。
  2. 这是 Java，而不是 C。有现成的数据结构可以轻松地做到这一点，程序员几乎不需要额外的努力。

来自Collections Framework 上的 Java 文档：

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

附录

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

这个“面试”是针对 Java 编程职位的。Java 作为一种面向对象的语言，能够执行诸如此类的任务，而无需从头开始设计流程（如在 C 和各种其他低级语言中）。此外，当考虑空间复杂性时，Java 不是最佳选择。也就是说，再次阅读我上面列表中的条目一。

于 2012-05-26T15:30:21.150 回答
4

Wikipedia 定义的线性散列具有增量调整大小的优点，因为桶以循环方式一个接一个地拆分，保持不变的摊销时间复杂度用于调整大小的插入。因此，他们的想法是迭代数组，重用已经迭代的元素作为线性散列的存储。

虽然我远不是线性哈希方面的专家，但我看不出有任何方法可以将哈希表放入数组中。当然，要使用线性散列存储 n 个元素，您可能会使用 n 个存储桶。但是，桶中的元素数量是无限的，您需要像链表这样的东西来实现每个桶，这需要额外的 O(n) 内存用于指针。

因此，该算法不会产生比普通算法更好的渐近空间复杂度HashSet。不过，它确实会以一个常数因子减少内存消耗。

它的时间复杂度与普通的不相上下HashSet。

编辑：在我看来，这个答案被忽略了（没有投票，没有评论）。它没有用吗？请发表评论，以便我知道要改进的地方。

于 2012-05-26T16:06:07.793 回答
2

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

要么面试没有说你必须“在没有其他数据结构的情况下”解决它，要么面试官实际上并不理解数据结构是一个数据结构，即使你自己实现了它。

无论如何，rofls，主要是因为这是您知道或不知道的那种问题。在面试中没有办法提出这个问题。我希望你不要为他们工作。

于 2012-05-26T15:28:39.327 回答
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 个元素，在迄今为止构建的散列表中搜索它们中的每一个，然后将它们散列到总是元素数量两倍的空间。继续此操作，直到 NC 数组元素被散列。搜索哈希表中剩余的 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. 遍历数组
  2. 使用二分搜索在所有前面的子数组中搜索当前元素。
  3. 将当前元素与前面的子数组一起排序，这些子数组对应于当前索引的二进制表示中的尾随“一”。例如，对于索引 87（1010111），我们需要将当前元素与 3 个子数组（1+1+2+4=8 个元素）一起排序。此步骤允许将当前元素添加到子数组，同时保持算法的不变性。
  4. 继续步骤 1 的下一次迭代。
于 2012-05-26T17:12:24.963 回答
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，则它们是第一个重复值的索引并且它是匹配的。

它只是比 O(n^2) 好一点，因为 j 永远不会覆盖 arr 的整个长度

于 2012-05-26T15:29:43.727 回答
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)

于 2012-05-28T08:31:21.923 回答
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));
}
于 2016-02-23T18:01:02.763 回答
0

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

  1. A 的长度 >= A 的最大值
  2. 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;
}

我在这里做的是使用数组本身来存储一些额外的信息。当我遍历数组时，每次遇到一个值时，我都会将该值用作索引。在此索引处，我将检查该值。如果值为负，我知道我以前来过这里（因为全是正约束）。因此，我找到了我的第一个副本，并且可以退出。否则，我将否定该索引处的值。

于 2018-05-17T15:21:24.910 回答