So, say you have 2 sets with unknown properties. So the order and the size of each set is unknown. How would we merge and sort these 2 sets into one set?
The solution I have is to simply add the 2 sets into one set and perform a merge sort.
I feel as if there is a better way. Does anyone have any ideas?
CodePudding user response：
Typically you would concatenate the sets and then sort them as a single set, that is almost as simple as it gets. I'm guessing you are using Python for this if that's the case you can use function sorted().
CodePudding user response：
A set is an unordered collection of unique elements => unordered , no duplicates
if two sets are disjoint sets => no common elements => directly union two sets
since, we don't know anything about 2 sets => first perform union and then remove duplicates.
For example, let us assume that we are using "linked list" to represent two sets.
For, set-1 => link_lis_1 => each element in set == a node in linked list
set-2 => link_lis_2
Now perform union of 2 sets => assign the last node 'next' pointer of link_lis_1 to
first node of link_lis_2 i.e, value in 'head' of link_lis_2
free(link_lis_2)
Time taken for union = O(n), where n = no. of elements in set-1.
here, order doesn't matter but elements should be unique
=> we need to remove duplicates from link_lis_1
below link contains methods to remove duplicates from linked list