C++で合計が最小のKペアを検索する

2つのソートされた配列A1とA2、および別の値kがあるとします。 A1の1つの要素とA2の別の要素で構成されるペア（u、v）を定義する必要があります。 [（u1、v1）、（u2、v2）、…、（uk、vk）]のようなkペアを見つける必要があります。したがって、A1 =[1、7、11]およびA2 =[2、4、6]、およびk =3の場合、出力は[（1、2）、（1、4）、（1、6）]になります。

これを解決するには、次の手順に従います-

• 2つの値aとb、およびインデックスをとる1つのデータ型を定義します。
• データ型のキーとデータのリストを値として受け取る優先度キューを1つ作成します。
• n：=A1のサイズ、m：=A2のサイズ
• nが0またはmが0の場合は、戻ります
• retと呼ばれる1つの行列を作成します
• 0からn–1の範囲のiの場合
  • （A1 [i]、A2 [0]、0）をデータとしてキューに挿入します
• キューが空ではなく、kが0でない場合、
  • curr：=キューの先頭、キュー要素を削除
  • currのfirst_val、currのsecond_valをretに挿入します
  • currのインデックス+1
  • （first_val of curr、A2 [index of curr + 1]、index of curr + 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,],]