Intersection of Three Sorted Arrays using Three Pointers

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

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

推荐阅读：
美丽的长沙作文200字　 不被理解又何妨作文600字　 整数小数改写、大小比较的知识　 各种数的读法和写法　 关于分数和百分数的知识点　 关于小数的知识点　 有关整数的知识点　 比较平均数、中位数、众数的特点　 小学统计图的种类及特点　 小学常用图形计算公式表　
评论列表
添加评论