跳到主要内容

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

· 阅读需 3 分钟

1、题干​

给你三个整数数组 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

2、思路1​

借助位运算、二进制，计算和存储数字出现次数，以消除重复数字产生的影响

3、代码​

function twoOutOfThree(nums1: number[], nums2: number[], nums3: number[]): number[] {
    const bucket = new Array(101).fill(0);
    const matrix = [nums1, nums2, nums3];

    for (let i = 0; i < matrix.length; i++) {
        for (const n of matrix[i]) bucket[n] = bucket[n] | (1 << i);
    }

    return bucket.map((c, n) => (c > 2 && c !== 4) ? n : 0).filter(Boolean);
};

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png

6、思路2​

哈希集合过滤数组中重复出现的数字

7、代码​

function twoOutOfThree(nums1: number[], nums2: number[], nums3: number[]): number[] {
    const s1 = new Set(nums1);
    const s2 = new Set(nums2);
    const s3 = new Set(nums3);
    const s4 = new Set([...nums1, ...nums2, ...nums3]);

    const ans = [];
    for (const n of s4) {
        const c = +s1.has(n) + +s2.has(n) + +s3.has(n);
        if (c > 1) ans.push(n);
    }

    return ans;
};

8、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

9、执行结果​

image.png