查找int数组中的第一个副本，java

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

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位| 到检查器，然后检查器到arrays中的下一个条目，检查它是否> 0。例如： 

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

但是这也是不允许的。

所以有一个暗示我可以将数组本身用作hashset / hashtable和“线性散列”？

任何帮助？ 谢谢

维基百科定义的线性散列具有以下优势：resize逐渐发生，因为循环以循环方式逐个拆分，保留用于插入resize的恒定摊销时间复杂度。 因此，他们的想法是迭代数组，重新使用已经迭代的元素作为线性散列的存储。

虽然我不是线性散列的专家，但我没有看到任何方法来适应数组中的散列表。 当然，要使用线性散列存储n个元素，您可以使用n个桶。 但是，存储桶中的元素数量是无限制的，您需要类似链接列表来实现每个存储桶，这会为指针花费额外的O（n）内存。

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

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

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

我有这个想法：当你向下进行数组时，你对你访问过的部分进行排序。 通过二进制搜索，您将改善时间; 空间是0.排序本身是…插入排序？ 您基本上正常运行排序，但是当您搜索插入新数字的位置时，如果您点击数字本身，则会喊出“宾果游戏”。 这是零空间+ O（n 2 ）时间的改进。

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

  1. 它开着）。 除非你做一些非常聪明的事情并将其归结为O（log n），否则你可能不会使用其他方法做得更好。
  2. 这是Java – 而不是C.有很容易获得的数据结构可以轻松地完成，而程序员几乎不需要额外的努力。

从集合框架上的Java文档 ：

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

附录

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

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

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

要么面试没有说你必须解决它“没有其他数据结构”，或者面试官确实不明白数据结构是一个数据结构，即使你自己实现它。

反正rofls，主要是因为这是你要么知道的问题，要么你不知道。 在面试中没有办法提出这个问题。 我希望你不会为他们工作。

这不使用线性散列，但比O（N 2 ）工作得更快：

  1. 选择一些小数字C并使用powershell算法查找数组的前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开始并被排序; 下一个这样的子arrays跟随它并且也被分类; 换句话说，当前索引的二进制表示描述了在它之前有多少个排序的子数组。 例如，对于索引87（1010111），我们在索引86处具有单个元素，在索引84处具有排序对，在80处具有4个元素的排序子数组，在64处具有16个元素的排序子数组，以及已排序数组开头的64个元素的子数组。

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

伪代码： 

 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）

我被提出这个额外的限制，没有额外的内存，只有寄存器。 这就是我提出的： 

 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是

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

这是平均算法上的O（n）时间 

 public static int firstRepeatingElement(int[] elements) { int index = -1; Set set = new HashSet(); 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)); }

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

  1. A的长度> = A的最大值
  2. A的所有值均为正值

通过这些额外的约束，我们可以使用更少的时间和空间来解决问题。

好的，我们来看看代码： 

 int findFirstDuplicateEntry(int[] A) { for (int i=0; i

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

Interesting Posts

如何规范Java中的EOL字符？

Java编程exception

为什么等待条件释放锁定但信号没有？

短路评估是否在C ++中得到保证，就像在Java中一样？

Jetty / SOLR管理员面板密码

使用String.split时转义逗号

并行扩展在Java中等效

如何将属性添加到应用程序上下文

日期和时间转换为java中的其他时区

使用selenium获取CSS属性值