Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 합이 가장 작은 K 쌍 찾기

<시간/>

두 개의 정렬된 배열 A1과 A2와 또 다른 값 k가 있다고 가정합니다. A1의 한 요소와 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)]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 하나의 데이터 유형을 정의하고 두 개의 값과 b, 색인을 사용합니다.
  • 유형 데이터의 키와 데이터 목록을 값으로 사용하는 하나의 우선 순위 대기열을 만듭니다.
  • n :=A1 크기, m :=A2 크기
  • n이 0이거나 m이 0이면 반환
  • ret라는 행렬 하나 만들기
  • 0 ~ n – 1 범위의 i에 대해
    • 대기열에 데이터로 (A1[i], A2[0], 0) 삽입
  • queue가 비어 있지 않고 k가 0이 아닌 경우
    • curr :=큐 상단, 큐 요소 삭제
    • curr의 first_val, curr의 second_val을 ret에 삽입
    • curr의 인덱스 + 1
    • (curr의 first_val, A2[curr의 인덱스 + 1], 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,],]