C++ map greedy observation
Intuition\n- The frequency of a number in an array is irrelevant; it will contribute at most once to the final count, whether it appears in one array or both.\n
# Intuition\n- The frequency of a number in an array is irrelevant; it will contribute at most once to the final count, whether it appears in one array or both.\n\n- It\'s unnecessary to strictly select n/2 numbers from both arrays. For example, consider nums1: [1, 2, 4, 4, 4, 4, 4, 4], nums2: [1, 2, 3, 4, 5, 6, 7, 8]. If we select distinct elements from nums1, such as [1, 2], which is less than n/2 = 4, we can include the numbers common to both arrays: [1, 2, 4]. Similarly, for nums2: [3, 5, 6, 7], resulting in the set [1, 2, 4, 5, 6, 7]. Even if nums1 had [1, 2, 4, 4], the final set would remain the same. This is because having fewer distinct elements than n/2 implies the presence of repeating numbers. Including repeating numbers won\'t affect the final set, as it is ensured to have distinct values.\n\n\n# Approach\n- For nums1 count dinstinct numbers that are not present in nums2.\n- If these distinct numbers are less than n/2, count distinct numbers that are present in both.\n- Similarly, for nums2, ensuring that common numbers already taken from nums1 are not considered again.\n\n\n# Code\n```\nclass Solution {\npublic:\n    int maximumSetSize(vector<int>& nums1, vector<int>& nums2) {\n        int n = nums1.size();\n        map<int, int> f1, f2;\n        for(auto &e:nums1) f1[e]++;\n        for(auto &e:nums2) f2[e]++;\n        int ans = 0;\n        int ct = 0;\n        for(auto &[e, v]:f1) {\n            if(ct == n/2) break;\n            if(f2.find(e)==f2.end()) ct++;\n        }\n        for(auto &[e, v]:f1) {\n            if(f2.find(e) == f2.end()) continue;\n            if(ct == n/2) break;\n            ct++;\n            f2[e] = INT_MAX;\n        }\n        ans += ct;\n\n        ct = 0;\n        for(auto &[e, v]:f2) {\n            if(ct == n/2) break;\n            if(f1.find(e)==f1.end()) ct++;\n        }\n        for(auto &[e, v]:f2) {\n            if(f1.find(e)==f1.end() || f2[e]==INT_MAX) continue; // if it\'s already counted in nums1\n            if(ct == n/2) break;\n            ct++;\n        }\n        return ans+ct;\n    }\n};\n```
['Hash Table', 'Greedy', 'C++']