CODEWITHSUNDEEP
algorithmsortingdata-structurescomputer-science
Ajay Bodhe
Ajay Bodhe

Reputation: 51

Is there any intersection find algorithm similar to union find when sets are not disjoint?

I want to find intersection of sets containing integer values? What is the most efficient way to do it if say you have 4-5 lists with 2k-4k integers?

Upvotes: 1

Views: 450

Answers (2)

Vikram Bhat
Vikram Bhat

Reputation: 6246

In many languages like for example c++ sets are implemented as balanced binary trees so you can directly evaluate set intersection in O(NlogM) use n as smaller set size by just looking up into the other set in O(logM).

Optimization :-

As you want it for multiple sets you can do the optimization that is used in huffman coding :-

  1. Use a priority queue of sets which selects smallest set first
  2. select two smallest sets first evaluate intersection and add it to queue.
  3. Do this till you get empty intersection set or one set(intersection set) remaining.

Note: Use std::set if using c++

Upvotes: 1

kuroi neko
kuroi neko

Reputation: 8661

If you have memory to spare:

  • Create a set that will hold the number of occurences of each value.
  • For each integer I in each of your set, increment the number of occurences of I
  • Extract integers with a number of occurences equal to the number of sets

This is theoretically in O(sum of all sets cardinalities + retrieval)

where retrieveal can be either the range of your integers (if you're using a raw array) or the cardinality of the union of your sets (if you're using a hash table to enumerate the values for which an occurence is defined).

If the bounds of your set are known and small, you can implement it with a simple array of integers big enough to hold the max number of sets (typically a 8 bits char for 256 sets).

Otherwise you'll need some kind of hash table, which should still theoretically be in o(n).

Upvotes: 0

Related Questions