The third way to find duplicate

Question

Two common ways to detect duplicates in an array:

1) sort first, time complexity O (n log n), space complexity O (1)

2) hash set, time complexity O (n), spatial complexity O (n)

Is there a third way to detect duplicate?

Please do not respond to brute force.

Answer 1

Another option is the Bloom filter. Complexity is O(n) , space is changing (almost always less than a hash), but there is a chance of false positives. There is a complex relationship between the size of the data set, the size of the filter, and the number of false positives that you can expect.

Flower filters are often used as quick “sanity checks” before performing more expensive duplicate checks.

Answer 2

Depends on the information.

If you know a range of numbers, for example 1-1000, you can use a bit array.

Assume that the range a ... b

Make an array bit with bits (ba). initialize them to 0.

Scroll the array when you get to the number x, change the bit in the place of xa to 1.

If there is already 1 there, you have a duplicate.

time complexity: O (n)

space complexity: (ba) bits

Answer 3

Another method for finding duplicates, provided that the array of n elements contains elements from 0 to n-1. < Find Duplicates >