查找第一个重复的int数组，爪哇 [英] Finding the first duplicate in an int array, java

问题描述

下面是一个常见的​​面试问题我碰到过，但是我未能改善它在它要求的方式。

 假设我们有一个int数组INT [] A，我们要找到的第一个重复条目。
 

1. 几乎每个人都可以想到使用HashSet的，并添加到它，而parsing.this会导致O（n）时间及O（n）的空间。此后，我被要求去解决它没有其他的数据结构。我说的是最愚蠢的想法会比较每一个在为O（n ^ 2）的时间。然后，我被要求提高为O（n ^ 2）的时间。

2. 和改进它，我想用一个固定大小的数组（假设的最大数量为n），布尔[] B =新的布尔[N]的;然而，我没有被允许使用这种方法。

3. 于是我想用一个int变量，采用位操作，如果最大数小于32，则对于n，我们可以把1到n位左右|一检查，然后和放大器;方格到阵列中的下一个条目，以判断是否> 0。 例如：

     INT C = A [1];
   如果（检查及（1＆LT; c为C）0）返回false;
   检查| = 1＆LT;＆LT; C;
    

然而，这是不允许的任一

因此​​就出现了，我可以使用数组本身作为HashSet的/哈希表，和线性散​​列的提示？

任何帮助吗？谢谢

解决方案

线性散列由维基百科定义有优势出现调整大小递增，因为水桶在循环方式被分割成一个接一个，保留用于插入并调整其大小恒定的摊余时间复杂度。因此，他们的想法是遍历数组，再利用已遍历作为存储线性散列的元素。

虽然我远在线性散列的专家，我看不到任何方式在阵列中以适合哈希表。诚然，以存储n线性散列的元素，你可能会得到通过使用N个区段。然而，在一个水桶是无界的元素个数，你需要像一个链表来实现每个桶，花费了指针的额外O（n）的内存。

因此​​，这种算法并不能产生更好的渐进空间复杂度比普通的的HashSet 。但它能够减少内存消耗常数因子，虽然。

它的时间复杂度是看齐，与普通的的HashSet 。

编辑：在我看来，这个答案被忽略（不带票，没有评论）。它是不是有用吗？请发表评论，所以我知道，以改善什么。

Here is a common interview question i came across, however i failed to improve it in the way it demands.

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

1. almost everyone can think of using a HashSet, and add to it while parsing.this will lead to O(n) time and O(n) space. After this I was asked to solve it without other data structures. I said the dumbest idea will be comparing each one in O(n^2) time. And then I was asked to improve the O(n^2) time.

2. And to improve it, i thought of using a fixed size array(assuming the maximum number is n), boolean[] b = new boolean[n]; however I was not allowed to use this method.

3. Then I thought of using an int variable, using bit manipulation, if the maximum number is smaller than 32, then for n we can push 1 to n bits left and | to a checker, then & the checker to the next entry in the array to check if it's > 0. e.g.:

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

however this is not allowed either.

So there was an hint that I can use the array itself as hashset/hashtable, and "linear hashing"?

any help ? thanks

解决方案

Linear hashing as defined by Wikipedia has the advantage that resizing occurs incrementally, because buckets are split one-by-one in round-robin fashion, retaining constant amortized time complexity for insertion with resize. Their idea therefore is to iterate over the array, reusing the elements already iterated over as storage for linear hashing.

While I am far from an expert on linear hashing, I don't see any way to fit the hash table in the array. Granted, to store n elements with linear hashing, you might get by with using n buckets. However, the number of elements in a bucket being unbounded, you'd need something like a linked list to implement each bucket, which costs an additional O(n) memory for pointers.

As such, this algorithm does not yield a better asymptotic space complexity than an ordinary HashSet. It does reduce memory consumption by a constant factor, though.

Its time complexity is on par with the ordinary HashSet.

Edit: It appears to me this answer is being ignored (no votes, no comments). Is it not useful? Please comment so I know what to improve.

这篇关于查找第一个重复的int数组，爪哇的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！