สมมติว่ามีอาร์เรย์จำนวนเต็ม 3 อาร์เรย์คือ arr1, arr2 และ arr3 ซึ่งเรียงลำดับเพิ่มขึ้นอย่างเคร่งครัด เราต้องคืนค่าอาร์เรย์ที่เรียงลำดับซึ่งประกอบด้วยจำนวนเต็มที่ปรากฏในทั้งสามอาร์เรย์ ตัวอย่างเช่น หากอาร์เรย์คือ [1,2,3,4,5], [1,2,5,7,9], และ [1,3,4,5,8] ผลลัพธ์จะเป็น [1,5]
ขั้นตอนการแก้ปัญหา
- กำหนดอาร์เรย์ชื่อ res
- สร้างแมป 3 ตัวคือ f1, f2 และ f3
- for i ในช่วง 0 ถึงความยาวของ arr1
- f1[arr1[i]] เพิ่มขึ้น 1
- for i ในช่วง 0 ถึงความยาวของ arr2
- f2[arr2[i]] เพิ่มขึ้น 1
- for i ในช่วง 0 ถึงความยาวของ arr3
- f3[arr3[i]] เพิ่มขึ้น 1
- for i = 1 ถึง 2000
- ถ้า f1[i] และ f2[i] และ f3[i] เป็นจริง
- แทรก i ลงในอาร์เรย์ res
- ถ้า f1[i] และ f2[i] และ f3[i] เป็นจริง
- คืนค่า res
ตัวอย่าง (C++):
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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));
}อินพุต
[1,2,3,4,5] [1,2,5,7,9] [1,3,4,5,8]
เอาต์พุต
[1,5]
