Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order.
Example 1:
Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3] Output: [3,2] Explanation: The values that are present in at least two arrays are: - 3, in all three arrays. - 2, in nums1 and nums2.
Example 2:
Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2] Output: [2,3,1] Explanation: The values that are present in at least two arrays are: - 2, in nums2 and nums3. - 3, in nums1 and nums2. - 1, in nums1 and nums3.
Example 3:
Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5] Output: [] Explanation: No value is present in at least two arrays.
Constraints:
1 <= nums1.length, nums2.length, nums3.length <= 1001 <= nums1[i], nums2[j], nums3[k] <= 100
Solution: Hashmap / Bitmask
s[x] := bitmask of x in all array[i]
s[x] = 101 => x in array0 and array2
Time complexity: O(n1 + n2 + n3)
Space complexity: O(n1 + n2 + n3)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) { unordered_map<int, int> s; for (int x : nums1) s[x] |= 1; for (int x : nums2) s[x] |= 2; for (int x : nums3) s[x] |= 4; vector<int> ans; for (auto [x, v] : s) if (__builtin_popcount(v) >= 2) ans.push_back(x); return ans; } }; |