Intersection of Three Sorted Arrays using Three Pointers

  • 时间：2020-09-18 17:39:21
  • 分类：网络文摘
  • 阅读：126 次

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

Example 1:
Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

Constraints:
1 <= arr1.length, arr2.length, arr3.length <= 1000
1 <= arr1[i], arr2[i], arr3[i] <= 2000

Hints:
Count the frequency of all elements in the three arrays.
The elements that appeared in all the arrays would have a frequency of 3.

Using Three Pointer Algorithm to Intersect Three Sorted Array

Since all the arrays are sorted, we can initialise three pointers pointing to each array. At each iteration, we need to compare three values, and moving the smallest pointer forward. If all elements are equal, then we find an intersection, which should be pushed to the end of the result array.

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

class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> res;
        int i = 0, j = 0, k = 0;
        int s1 = arr1.size(), s2 = arr2.size(), s3 = arr3.size();
        while ((i < s1) && (j < s2) && (k < s3)) {
            if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) {
                res.push_back(arr1[i]);
                i ++; j ++; k ++; continue;
            }
            if (arr1[i] < arr2[j]) {
                i ++;
                continue;
            } else if (arr1[i] &t; arr2[j]) {
                j ++;
                continue;
            }
            if (arr1[i] < arr3[k]) {
                i ++;
                continue;
            } else if (arr1[i] > arr3[k]) {
                k ++;
                continue;
            }
            if (arr2[j] < arr3[k]) {
                j ++;
                continue;
            } else if (arr2[j] > arr3[k]) {
                k ++;
                continue;
            }
        }
        return res;
    }
};
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> res;
        int i = 0, j = 0, k = 0;
        int s1 = arr1.size(), s2 = arr2.size(), s3 = arr3.size();
        while ((i < s1) && (j < s2) && (k < s3)) {
            if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) {
                res.push_back(arr1[i]);
                i ++; j ++; k ++; continue;
            }
            if (arr1[i] < arr2[j]) {
                i ++;
                continue;
            } else if (arr1[i] &t; arr2[j]) {
                j ++;
                continue;
            }
            if (arr1[i] < arr3[k]) {
                i ++;
                continue;
            } else if (arr1[i] > arr3[k]) {
                k ++;
                continue;
            }
            if (arr2[j] < arr3[k]) {
                j ++;
                continue;
            } else if (arr2[j] > arr3[k]) {
                k ++;
                continue;
            }
        }
        return res;
    }
};

The comparisons are a bit repetive – which we can simplify a bit without putting too much efforts on the every little branch/details.

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) {
        vector<int> res;
        int i = 0, j = 0, k = 0;
        int s1 = arr1.size(), s2 = arr2.size(), s3 = arr3.size();
        while ((i < s1) && (j < s2) && (k < s3)) {
            if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) {
                res.push_back(arr1[i]);
                i ++; j ++; k ++; continue;
            }
            if (arr1[i] < arr2[j]) {
                i ++;
            } else if (arr2[j] < arr3[k]) {
                j ++;
            } else {
                k ++;
            }
        }
        return res;
    }
};
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> res;
        int i = 0, j = 0, k = 0;
        int s1 = arr1.size(), s2 = arr2.size(), s3 = arr3.size();
        while ((i < s1) && (j < s2) && (k < s3)) {
            if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) {
                res.push_back(arr1[i]);
                i ++; j ++; k ++; continue;
            }
            if (arr1[i] < arr2[j]) {
                i ++;
            } else if (arr2[j] < arr3[k]) {
                j ++;
            } else {
                k ++;
            }
        }
        return res;
    }
};

We can also increment the pointer that has the minimal value among the three.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> res;
        int i = 0, j = 0, k = 0;
        int s1 = arr1.size(), s2 = arr2.size(), s3 = arr3.size();
        while ((i < s1) && (j < s2) && (k < s3)) {
            if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) {
                res.push_back(arr1[i]);
                i ++; j ++; k ++; continue;
            }
            int curMin = min(arr1[i], min(arr2[j], arr3[k]));
            if (arr1[i] == curMin) i ++;
            if (arr2[j] == curMin) j ++;
            if (arr3[k] == curMin) k ++;
        }
        return res;
    }
};
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> res;
        int i = 0, j = 0, k = 0;
        int s1 = arr1.size(), s2 = arr2.size(), s3 = arr3.size();
        while ((i < s1) && (j < s2) && (k < s3)) {
            if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) {
                res.push_back(arr1[i]);
                i ++; j ++; k ++; continue;
            }
            int curMin = min(arr1[i], min(arr2[j], arr3[k]));
            if (arr1[i] == curMin) i ++;
            if (arr2[j] == curMin) j ++;
            if (arr3[k] == curMin) k ++;
        }
        return res;
    }
};

All the above three-way merge algorithms take O(N) time and O(1) constant space (excluding the usage of result array).

Intersection Three Arrays using Hash Set

Modern programming languages often allow you to do these tasks easily with one-liner. For example, in Javascript, you can use the Array.filter() with the Arrays.includes() method without implementing the details. However, this does not benefit from the fact that the arrays are sorted. The complexity is O(N^2) – and you have to do it twice.

1
2
3
4
5
6
7
8
9
10

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @param {number[]} arr3
 * @return {number[]}
 */
var arraysIntersection = function(arr1, arr2, arr3) {
    return arr1.filter(el => arr2.includes(el))
        .filter(el => arr3.includes(el));
};
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @param {number[]} arr3
 * @return {number[]}
 */
var arraysIntersection = function(arr1, arr2, arr3) {
    return arr1.filter(el => arr2.includes(el))
        .filter(el => arr3.includes(el));
};

Given in Python, these can be done even quickly. For example, we can convert the array to set, and using the inbuild intersection with & operator. Then, we just need to return the sorted version of the set.

1
2
3

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        return sorted(set(arr1) & set(arr2) & set(arr3))
class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        return sorted(set(arr1) & set(arr2) & set(arr3))

The sorting takes O(N.LogN), and converting array to set takes O(N). The intersection of two sets take O(N). We can also do this quite natively using list comprehension.

1
2
3

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        return [a for a in arr1 if a in arr2 and a in arr3]
class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        return [a for a in arr1 if a in arr2 and a in arr3]

Another solution is to count and sum up the frequency of numbers in three arrays using the hash map (dictionary). Then we just need to count those numbers that appear three times.

1
2
3
4
5
6

import collections
 
class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        cnt = collections.Counter(arr1) + collections.Counter(arr2) + collections.Counter(arr3)
        return [x for x in cnt if cnt[x] == 3]
import collections

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        cnt = collections.Counter(arr1) + collections.Counter(arr2) + collections.Counter(arr3)
        return [x for x in cnt if cnt[x] == 3]

The counting can be easily done using Pythonic way: the collections.Counter(). You may also be interested in How to Find Intersection of Two Arrays in C++?

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
诗词名句鉴赏：风萧萧兮易水寒，壮士一去兮不复还!　 申胥谏许越成原文及翻译　 诸稽郢行成于吴原文及翻译　 诗词名句鉴赏：秋风起兮白云飞，草木黄落兮雁南归。　 王孙圉论楚宝原文及翻译　 根据营业额算税款　 根据税款算收入的数学问题　 鸡兔同笼变式题　 求火车速度和车长　 货车的长度是多少米　
评论列表
添加评论