LeetCode

2248. Intersection of Multiple Arrays

文章目录
  1. 1. 题目
  2. 2. 思路

题目


https://leetcode.com/problems/intersection-of-multiple-arrays/

思路

这道题我第一反应是用动态解析，不断地比对交集并且进行记录。但是马上我意识到我可能把这道题想得复杂了一些。从结果来思考，结果必然同时存在于所有的数组中，那么我们只需要用第一个数组和后续数组进行交集比对，把相交结果存在一个新的数组中，用这个新数组来继续和后续数组进行交集比对，比对一轮之后剩下的就是结果。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def intersection(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        result = set(nums[0])
        for num in nums:
            result= result & set(num)
        return sorted(list(result))

同时根据Discuss中的答案上，有说使用C++的map函数来做的，我看了看map的用法，应该是通过循环遍历map，value值和arr.size()相等则意味着它在每个数组中都出现过，即是我们需要的交集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        map<int, int> ump;
        for(int i = 0; i < nums.size(); ++i)
            for(int j = 0; j < nums[i].size(); ++j)
                ump[nums[i][j]]++;
        vector<int> res;
        for(auto it = ump.begin(); it != ump.end(); ++it)
            if(it->second == nums.size())
                res.push_back(it->first);
        return res;
    }
};

// In here we cannot use unordered_map, otherwise we will need to sort res

另外好像存在第三种，递归的算法，我没看明白和set的区别。
https://leetcode.cn/problems/intersection-of-multiple-arrays/solution/by-nehzil-9383/

还有一个两行的算法，我看这种又短又复杂的会头晕….

1
2
3
class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        return sorted(reduce(set.__iand__, map(set, nums)))

2022/5/28更新

我最近在看CMU 213这门课，发现原来这道题可以直接用位运算的&运算符来做，但是在discuss中的C++. Fast. Low memory. Bitset based solution.我不太看得明白，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        static_assert(sizeof(unsigned long) == 8);
        uint64_t acc[16], buf[16];
        memset(acc, -1, sizeof(acc));
        for (auto &arr : nums) {
            memset(buf, 0, sizeof(buf));
            for (int v : arr) {
                buf[v >> 6] |= 1llu << (v & 0x3f);
            }
            for (int i=0; i < 16; i++) acc[i] &= buf[i];
        }
        vector<int> ans;
        for (int i=0, v=0; i < 16; i++, v=i<<6) {
            uint64_t b = acc[i];
            while (b) {
                ans.push_back(v + __builtin_ctzl(b));
                b ^= b & -b;
            }
        }
        return ans;
    }
};