สมมติว่าเรามีอาร์เรย์ที่เรียงลำดับสอง A1 และ A2 และอีกค่าหนึ่งคือ k เราต้องกำหนดคู่ (u, v) ซึ่งประกอบด้วยองค์ประกอบหนึ่งจาก A1 และองค์ประกอบอื่นจาก A2 เราต้องหาคู่ k เช่น [(u1, v1), (u2, v2),…, (uk, vk)] ดังนั้นหาก A1 =[1, 7, 11] และ A2 =[2, 4, 6] และ k =3 ผลลัพธ์จะเป็น [(1, 2), (1, 4), (1, 6)]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดประเภทข้อมูลหนึ่งประเภท โดยจะรับสองค่า a และ b และดัชนี
- สร้างคิวลำดับความสำคัญหนึ่งรายการ ซึ่งจะรับคีย์ข้อมูลประเภทและรายการข้อมูลเป็นค่า
- n :=ขนาด A1, m :=ขนาด A2
- ถ้า n เป็น 0 หรือ m เป็น 0 ให้คืนค่า
- สร้างเมทริกซ์ที่เรียกว่า ret
- สำหรับ i ในช่วง 0 ถึง n – 1
- แทรก (A1[i], A2[0], 0) เป็นข้อมูลลงในคิว
- ในขณะที่คิวไม่ว่าง และ k ไม่ใช่ 0 แล้ว
- curr :=ด้านบนของคิว ลบองค์ประกอบคิว
- ใส่ first_val ของ curr, second_val ของ curr ลงใน ret
- ถ้าดัชนีของสกุลเงิน + 1 <ม. แล้ว
- แทรกข้อมูลด้วย (first_val ของสกุลเงิน, A2[ดัชนีของสกุลเงิน + 1], ดัชนีของสกุลเงิน + 1), ลงในคิว
- ลด k ขึ้น 1
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
#include <stack>
using namespace std;
struct Data{
int firstVal, secondVal, idx;
Data(int a, int b, int c){
firstVal = a;
secondVal = b;
idx = c;
}
};
struct Comparator{
bool operator()(Data a, Data b){
return !(a.firstVal + a.secondVal < b.firstVal + b.secondVal);
}
};
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue <Data, vector <Data>, Comparator> pq;
int n = nums1.size();
int m = nums2.size();
if(!n || !m)return {};
vector < vector <int> > ret;
for(int i = 0; i < n; i++){
pq.push(Data(nums1[i], nums2[0], 0));
}
while(!pq.empty() && k--){
Data curr = pq.top();
pq.pop();
ret.push_back({curr.firstVal, curr.secondVal});
if(curr.idx + 1 < m){
pq.push(Data(curr.firstVal, nums2[curr.idx + 1], curr.idx + 1));
}
}
return ret;
}
};
void print(vector <int> const &arr) {
cout<<"[";
for(int i=0; i < arr.size(); i++)
std::cout << arr.at(i) <<",";
cout<<"]";
}
int main() {
vector<int> nums1{1,7,11};
vector<int> nums2{2,4,6};
int k = 3;
Solution ob1;
vector<vector<int>> numsRet;
numsRet = ob1.kSmallestPairs(nums1, nums2, k);
cout<<"[";
for (vector<int> x : numsRet) {
print(x);
cout<<",";
}
cout<<"]"<<endl;
return 0;
} อินพุต
[1,7,11]
[2,4,6]
3
vector<int> nums1{1,7,11};
vector<int> nums2{2,4,6};
int k = 3;
Solution ob1;
vector<vector<int>> numsRet;
numsRet = ob1.kSmallestPairs(nums1, nums2, k); ผลลัพธ์
[[1,2,],[1,4,],[1,6,],]
