Giao của ba mảng đã sắp xếp trong C++

Giả sử có ba mảng nguyên arr1, arr2, arr3 được sắp xếp theo thứ tự tăng chặt, ta cần trả về mảng đã sắp xếp chỉ chứa các số nguyên xuất hiện trong cả ba mảng. Ví dụ, nếu các mảng là [1,2,3,4,5], [1,2,5,7,9], và [1,3,4,5,8], đầu ra sẽ là [1,5].

Để giải quyết, ta làm theo các bước:

• Định nghĩa mảng res
• Tạo ba bảng băm f1, f2, f3
• Với i từ 0 đến độ dài arr1: f1[arr1[i]] tăng 1
• Với i từ 0 đến độ dài arr2: f2[arr2[i]] tăng 1
• Với i từ 0 đến độ dài arr3: f3[arr3[i]] tăng 1
• Với i = 1 đến 2000: nếu f1[i] và f2[i] và f3[i] đều khác 0, thêm i vào res
• Trả về res

Ví dụ (C++):

Xem triển khai sau để hiểu rõ hơn:

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<int> v){ 
    cout << "["; 
    for(int i = 0; i < v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]" << endl; 
} 

class Solution { 
public: 
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) { 
        vector<int> ans; 
        unordered_map<int,int> f1, f2, f3; 
        for(int i = 0; i < arr1.size(); i++){ 
            f1[arr1[i]]++; 
        } 
        for(int i = 0; i < arr2.size(); i++){ 
            f2[arr2[i]]++; 
        } 
        for(int i = 0; i < arr3.size(); i++){ 
            f3[arr3[i]]++; 
        } 
        for(int i = 1; i <= 2000; i++){ 
            if(f1[i] && f2[i] && f3[i]) ans.push_back(i); 
        } 
        return ans; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v1 = {1,2,3,4,5}; 
    vector<int> v2 = {1,2,5,7,9}; 
    vector<int> v3 = {1,3,4,5,8}; 
    print_vector(ob.arraysIntersection(v1, v2, v3)); 
    return 0;
}

Đầu vào

[1,2,3,4,5] [1,2,5,7,9] [1,3,4,5,8]

Đầu ra

[1,5]