LeetCode Daily 11

2022-1-14 T.373 查找和最小的K对数字

　　　　c++11 的新特性-----Tuple

题目描述：

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

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

请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。

示例：

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

思路：

Tuple 是固定大小不同值的集合，是pair的泛化、升级版。保存三个及以上的数据使用。

用一个set存储 tuple：nums1和nums2的和，nums1的下标，nums2的下标。

逐个更新set中的值，利用set自动排序的特性，每次选出和最小的值，通过下标加入res中。

代码：

class Solution {
public:
    vectorint>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        setint, int, int>> s;
        s.insert({nums1[0] + nums2[0], 0, 0});
        vectorint>> res;
        while(res.size() < k && s.size()) {
            auto x = *s.begin();
            int a = get<1>(x), b = get<2>(x); //tuple的get方法：get<位置下标>（数值对象）
            s.erase(s.begin());
            res.push_back({nums1[a], nums2[b]});
            if(a + 1 < nums1.size()) {
                s.insert({nums1[a + 1] + nums2[b], a + 1, b});
            }
            if(b + 1 < nums2.size()) {
                s.insert({nums1[a] + nums2[b + 1], a, b + 1});
            }
        }
        return res;
    }
};