Intersection of Three Sorted Arrays using Three Pointers

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

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

推荐阅读：
整数四则运算的意义和各部分名称　 数学中学过的性质和规律　 小数分数百分数互相转化方法　 美丽的南湖作文　 圣诞节的礼物_关于描写礼物的小学生作文300字　 做人　 “谈”赛尔号 网游　 美丽的郑州作文　 春节习俗作文400字600字　 中国风の　
评论列表
添加评论