Find a unique common element from 3 arrays

Question

Original issue:
I have 3 boxes, each of which contains 200 coins, given that there is only one person who made calls from all three boxes, and thus, each box has one coin with the same fingerprints, and the rest of all coins has different fingerprints. You should find a coin that contains the same fingerprint from all three boxes. So that we can find the fingerprint of the person who called from all three boxes.

Converted Problem:
You have 3 arrays containing 200 integers each. Given that in these three arrays there is one and only one common element. Find a common item.
Think of this solution, except for the trivial space O (1) and time O (n ^ 3).

Answer 1

Some improvement in Pelkonen's answer:
From the converted task to OP:

"Given that in these three arrays there is one and only one common element."

We need to sort only 2 arrays and find a common element.

Answer 2

If you sort all arrays first O (n log n), then it will be pretty easy to find a common element less than O (n ^ 3) time. You can, for example, use binary search after sorting them.

Answer 3

Let N = 200, k = 3,

• Create a hash table H with capacity ≥ Nk.

• For each element X in array 1, set H [X] to 1.

• For each element Y in array 2, if Y is in H and H [Y] == 1, set H [Y] = 2.

• For each element Z in array 3, if Z is in H and H [Z] == 2, return Z.

• throw new InvalidDataGivenByInterviewerException();

O (Nk), the complexity of the space O (Nk).

Answer 4

Use a hash table for each integer and encode entries in which you know from which array it appears - then check if there is a slot that contains entries from all three arrays. O (n)

Answer 5

Use hash table display objects to calculate frequency. Iterate over all three lists, increasing the number of matches in the hash table, until you come across a number with the number of occurrences of 3. This is O (n), since sorting is not required. An example in Python:

 def find_duplicates(*lists): num_lists = len(lists) counts = {} for l in lists: for i in l: counts[i] = counts.get(i, 0) + 1 if counts[i] == num_lists: return i 

Or equivalent using sets:

 def find_duplicates(*lists): intersection = set(lists[0]) for l in lists[1:]: intersection = intersection.intersect(set(l)) return intersection.pop() 

Answer 6

O (N): Use a hash table. H [i] = list of all integers in three arrays that map to i.

For all H [i]> 1, check if its three values ​​coincide. If yes, you have your own decision. You can even perform this test with a naive solution, it should still be very fast, or you can sort these H [i] and then it becomes trivial.

If your numbers are relatively small, you can use H [i] = k, if I appear k times in three arrays, then the solution is i, for which H [i] = 3. If your numbers are huge, use a hash table, although .

You can expand this to work, even if you can have elements that can be shared only by two arrays, and also if you can have elements repeating elements in one of the arrays. It just gets a little trickier, but you should be able to figure it out yourself.

Answer 7

If you need the fastest * answer:

• Sorting one array - time N log N.
• For each element in the second array, search for the first. If you find it, add 1 to the companion array; otherwise add 0 - time N log N using space N.
• For each nonzero account, copy the corresponding record into a temporary array, compacting it so that it is still sorted - time is N.
• For each element in the third array, search for a temporary array; when you find a hit, stop. Time is less than N log N.

Here is the code in Scala that illustrates this:

 import java.util.Arrays val a = Array(1,5,2,3,14,1,7) val b = Array(3,9,14,4,2,2,4) val c = Array(1,9,11,6,8,3,1) Arrays.sort(a) val count = new Array[Int](a.length) for (i <- 0 until b.length) { val j =Arrays.binarySearch(a,b(i)) if (j >= 0) count(j) += 1 } var n = 0 for (i <- 0 until count.length) if (count(i)>0) { count(n) = a(i); n+= 1 } for (i <- 0 until c.length) { if (Arrays.binarySearch(count,0,n,c(i))>=0) println(c(i)) } 

With a bit more complexity, you can either use the extra space due to the even more destructive action of your original arrays, or you can not touch the original arrays at all due to another N.

---

Edit: * as comments noted, hash tables are faster for non-perverted inputs. This is the "fastest worst case." The worst case may not be so unlikely if you are not using a really good hashing algorithm that could well eat longer than yours. For example, if you multiply all your values ​​by 2 ^ 16, trivial hashing (i.e. just use the bit number as an index) will come up each time in lists shorter than 64k ....