19 查找和最小的K对数字（373）

作者: Turbo时间限制: 1S章节: DS:队列

晚于: 2020-07-15 12:00:00后提交分数乘系数50%

截止日期: 2020-07-22 12:00:00

问题描述 :

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。

找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)，按从小到大的顺序输出它们的和。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3

输出: 因为前三对是：[1,2],[1,4],[1,6]，所以输出3，5，7

解释: 返回序列中的前 3 对数：

     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2

输出: 2, 2

解释: 返回序列中的前 2 对数：

     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3 

输出: 总共只有两对：[1,3],[2,3]，所以输出4, 5

解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

可使用以下main函数：

int main()

{

    int n,m,data,k;

    vector<int> nums1,nums2;

    cin>>n;

    for(int i=0; i<n; i++)

    {

        cin>>data;

        nums1.push_back(data);

    }

    cin>>m;

    for(int i=0; i<m; i++)

    {

        cin>>data;

        nums2.push_back(data);

    }

    cin>>k;

    vector<vector<int> > res=Solution().kSmallestPairs(nums1,nums2,k);

    for(int i=0; i<res.size(); i++)

    {

        if (i>0)

            cout<<" ";

        cout<<res[i][0]+res[i][1];

    }

    return 0;

}

输入说明 :

首先输入nums1的长度n，然后输入n个整数

再输入nums2的长度m，然后输入m个整数

最后输入k

输出说明 :

按从小到大的顺序输出k对数字的和（注意：可能不足k对）

输入范例 :

3 1 7 11 3 2 4 6 3

输出范例 :

3 5 7

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    struct Point
    {
        int x, y, sum;
        Point(int _x, int _y) :x(_x), y(_y), sum(_x + _y) {};
        bool operator <(const Point& p)const
        {
            return sum < p.sum;
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        priority_queue<Point> Q;
        for (auto a : nums1)
            for (auto b : nums2)
            {
                Q.push({ a,b });
                if (Q.size() > k) 
                    Q.pop();
            }
        vector<vector<int> > res;
        while (!Q.empty())
        {
            auto p = Q.top();
            res.push_back({ p.x,p.y });
            Q.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};


int main()
{
    int n,m,data,k;
    vector<int> nums1,nums2;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>data;
        nums1.push_back(data);
    }
    cin>>m;
    for(int i=0; i<m; i++)
    {
        cin>>data;
        nums2.push_back(data);
    }
    cin>>k;
    vector<vector<int> > res=Solution().kSmallestPairs(nums1,nums2,k);
    for(int i=0; i<res.size(); i++)
    {
        if (i>0)
            cout<<" ";
        cout<<res[i][0]+res[i][1];
    }
    return 0;
}