用C ++查找最小对的K对

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个排序数组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，A2 [curr的索引+ 1]，curr的索引+1）插入队列中

    • curr：=队列顶部，删除队列元素

    • 将curr的first_val和curr的second_val插入ret

    • 如果curr的索引+ 1 <m，则

    • 将k减1

  • 返回ret

让我们看下面的实现以更好地理解-

示例

#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,],]

以上是 用C ++查找最小对的K对 的全部内容， 来源链接： utcz.com/z/347425.html

回到顶部