Mind palace

some thoughts

0%

1213. Intersection of Three Sorted Arrays

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

O(mn) time O(1) space
类似merge的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        int i = 0, j = 0, k = 0, n1 = arr1.size(), n2 = arr2.size(), n3 = arr3.size();
        vector<int> res;
        while (i < n1 && j < n2 && k < n3) {
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                res.push_back(arr1[i]);
            }
            int mn = min({arr1[i], arr2[j], arr3[k]}); // 因为当前的三个数不同所以找出最小的数并跳过
            if (mn == arr1[i]) {
                ++i;
            }
            if (mn == arr2[j]) {
                ++j;
            }
            if (mn == arr3[k]) {
                ++k;
            }
        }
        return res;
    }
};
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> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        int i = 0, j = 0, k = 0, n1 = arr1.size(), n2 = arr2.size(), n3 = arr3.size();
        vector<int> res;
        while (i < n1 && j < n2 && k < n3) {
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) { // 如果三个数都一样则输出
                res.push_back(arr1[i]);
                ++i;
                ++j;
                ++k;
            } else if (arr1[i] < arr2[j]) { // 如果arr1[i]不是最大则看arr1[i + 1]
                ++i;
            } else if (arr2[j] < arr3[k]) { // 如果arr2[j]不是最大则看arr2[j + 1]
                ++j;
            } else { // 如果arr3[k]不是最大则看arr3[k + 1]
                ++k;
            }
        }
        return res;
    }
};

O(mn) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        unordered_map<int, int> m;
        for (int x : arr1) {
            ++m[x];
        }
        unordered_map<int, int> t;
        for (int x : arr2) {
            if (m.count(x)) {
                if (--m[x] == 0) {
                    m.erase(x);
                }
                ++t[x];
            }
        }
        t.swap(m);
        t.clear();
        for (int x : arr3) {
            if (m.count(x)) {
                if (--m[x] == 0) {
                    m.erase(x);
                }
                ++t[x];
            }
        }
        t.swap(m);
        t.clear();
        vector<int> res;
        for (auto [k, v] : m) {
            for (int i = 0; i < v; ++i) {
                res.push_back(k);
            }
        }
        sort(begin(res), end(res));
        return res;
    }
};