Intersection of Three Sorted Arrays using Three Pointers

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

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) —

推荐阅读：
初有所成，静待花开　 端午包粽子作文350字　 成长的温暖作文900字　 沙家浜作文400字　 中秋节作文1400字：思念在那个秋天　 夜晚的华尔兹　 擀面皮作文400字　 爷爷——我因你而骄傲|小学作文　 再隔多远又有一根电线杆不必移动　 小明房间的地面至少是多少平方米　
评论列表
添加评论