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).