Intersection of Three Sorted Arrays using Three Pointers

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

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

推荐阅读：
常吃这些食物可让你拥有健康的牙齿　 转基因食品安全立法的不足和完善建议　 食品添加剂过量对人体健康带来的危害　 揭秘零食里面的食品添加剂及其危害　 食品学专家解析转基因食品安全问题　 最有利于秋季养生的果蔬食物大盘点　 对眼睛视力保护最有好处的10种食物　 多吃4类富含维生素的食物给眼睛补营养　 人工营养素和天然营养素有何区别　 红枣养生食疗：养肝排毒安神补血养颜　
评论列表
添加评论