2032-至少在两个数组中出现的值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你三个整数数组 nums1、nums2 和 nums3 ，请你构造并返回一个 元素各不相同的 数组，且由 至少 在
两个 数组中出现的所有值组成 。 数组中的元素可以按 任意 顺序排列。

示例 1：

**输入：** nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
**输出：** [3,2]
**解释：** 至少在两个数组中出现的所有值为：
- 3 ，在全部三个数组中都出现过。
- 2 ，在数组 nums1 和 nums2 中出现过。

示例 2：

**输入：** nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
**输出：** [2,3,1]
**解释：** 至少在两个数组中出现的所有值为：
- 2 ，在数组 nums2 和 nums3 中出现过。
- 3 ，在数组 nums1 和 nums2 中出现过。
- 1 ，在数组 nums1 和 nums3 中出现过。

示例 3：

**输入：** nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
**输出：** []
**解释：** 不存在至少在两个数组中出现的值。

提示：

  • 1 <= nums1.length, nums2.length, nums3.length <= 100
  • 1 <= nums1[i], nums2[j], nums3[k] <= 100

方法一：哈希表

思路与算法

题目给出三个整数数组 nums}_1、nums}_2 和 nums}_3。现在我们需要求一个元素各不相同的数组，其中的元素为至少在数组 nums}_1、nums}_2 和 nums}_3 中两个数组出现的全部元素。

我们可以用「哈希表」来实现——由于只有三个数组，所以我们一个整数的最低三个二进制位来标记某一个数在哪几个数组中，1 表示该数在对应的数组中的，反之 0 表示不在。最后我们只需要判断每一个数对应的标记数字中二进制位个数是否大于 1 即可。

代码

[sol1-Python3]
1
2
3
4
5
6
7
class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        mask = defaultdict(int)
        for i, nums in enumerate((nums1, nums2, nums3)):
            for x in nums:
                mask[x] |= 1 << i
        return [x for x, m in mask.items() if m & (m - 1)]
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        unordered_map<int, int> mp;
        for (auto& i : nums1) {
            mp[i] = 1;
        }
        for (auto& i : nums2) {
            mp[i] |= 2;
        }
        for (auto& i : nums3) {
            mp[i] |= 4;
        }
        vector<int> res;
        for (auto& [k, v] : mp) {
            if (v & (v - 1)) {
                res.push_back(k);
            }
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i : nums1) {
            map.put(i, 1);
        }
        for (int i : nums2) {
            map.put(i, map.getOrDefault(i, 0) | 2);
        }
        for (int i : nums3) {
            map.put(i, map.getOrDefault(i, 0) | 4);
        }
        List<Integer> res = new ArrayList<Integer>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int k = entry.getKey(), v = entry.getValue();
            if ((v & (v - 1)) != 0) {
                res.add(k);
            }
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public IList<int> TwoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        IDictionary<int, int> dictionary = new Dictionary<int, int>();
        foreach (int i in nums1) {
            dictionary.TryAdd(i, 1);
        }
        foreach (int i in nums2) {
            dictionary.TryAdd(i, 0);
            dictionary[i] |= 2;
        }
        foreach (int i in nums3) {
            dictionary.TryAdd(i, 0);
            dictionary[i] |= 4;
        }
        IList<int> res = new List<int>();
        foreach (KeyValuePair<int, int> pair in dictionary) {
            int k = pair.Key, v = pair.Value;
            if ((v & (v - 1)) != 0) {
                res.Add(k);
            }
        }
        return res;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define MAX_NUM 100

int* twoOutOfThree(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* returnSize) {
    int mp[MAX_NUM + 1];
    memset(mp, 0, sizeof(mp));
    for (int i = 0; i < nums1Size; i++) {
        mp[nums1[i]] = 1;
    }
    for (int i = 0; i < nums2Size; i++) {
        mp[nums2[i]] |= 2;
    }
    for (int i = 0; i < nums3Size; i++) {
        mp[nums3[i]] |= 4;
    }
    int *res = (int *)malloc(sizeof(int) * MAX_NUM);
    int pos = 0;
    for (int i = 1; i <= MAX_NUM; i++) {
        if (mp[i] & (mp[i] - 1)) {
            res[pos++] = i;
        }
    }
    *returnSize = pos;
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var twoOutOfThree = function(nums1, nums2, nums3) {
    const map = new Map();
    for (const i of nums1) {
        map.set(i, 1);
    }
    for (const i of nums2) {
        map.set(i, (map.get(i) || 0) | 2);
    }
    for (const i of nums3) {
        map.set(i, (map.get(i) || 0) | 4);
    }
    const res = [];
    for (const [k, v] of map.entries()) {
        if ((v & (v - 1)) !== 0) {
            res.push(k);
        }
    }
    return res;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func twoOutOfThree(nums1, nums2, nums3 []int) (ans []int) {
	mask := map[int]int{}
	for i, nums := range [][]int{nums1, nums2, nums3} {
		for _, x := range nums {
			mask[x] |= 1 << i
		}
	}
	for x, m := range mask {
		if m&(m-1) > 0 {
			ans = append(ans, x)
		}
	}
	return
}

复杂度分析

  • 时间复杂度：O(n_1 + n_2 + n_3)，其中 n_1，n_2，n_3 分别为数组 nums}_1，nums}_2，nums}_3 的长度。
  • 空间复杂度：O(n_1 + n_2 + n_3)，其中 n_1，n_2，n_3 分别为数组 nums}_1，nums}_2，nums}_3 的长度，主要为哈希表的空间开销。
 Comments
On this page
2032-至少在两个数组中出现的值