leetcode 373. Find K Pairs with Smallest Sums 暴力循环求解-蒲公英云

leetcode 373. Find K Pairs with Smallest Sums 暴力循环求解

蔚落 2022-06-07 02:47 251阅读 0赞

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

Example 1:
Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2

Return: [1,1],[1,1]

The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Given nums1 = [1,2], nums2 = [3], k = 3

Return: [1,3],[2,3]

All possible pairs are returned from the sequence:
[1,3],[2,3]

直接暴力实现吧，反正Accept了。

代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/*
 * 直接暴力去做把，我这里使用的是排序，也可以使用堆
 * */
class Solution 
{
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) 
    {
        List<int[]> res=new ArrayList<>();
        List<int[]> all=new ArrayList<>();
        for(int i=0;i<nums1.length;i++)
        {
            for(int j=0;j<nums2.length;j++)
            {
                all.add(new int[]{nums1[i] , nums2[j]});
            }
        }
        Collections.sort(all, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return (a[0]+a[1])-(b[0]+b[1]);
            }
        });
        if(k<all.size())
        {
            for(int i =0;i<k;i++)
                res.add(all.get(i));
        }else 
            res.addAll(all);
        return res;
    }
}

下面是C++的做法，直接暴力然后排序即可

我们也可以使用multimap来做，思路是我们将数组对之和作为key存入multimap中，利用其自动排序的机制，这样我们就可以省去sort的步骤，最后把前k个存入res中即可。

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
using namespace std;
bool cmp(pair<int, int> &a, pair<int, int> &b)
{
    return a.first + a.second < b.first + b.second;
}
class Solution 
{
public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) 
    {
        vector<pair<int, int>> all;
        for (int i = 0; i < min(k,(int)nums1.size()); i++)
        {
            for (int j = 0; j < min(k, (int)nums2.size()); j++)
            {
                all.push_back({nums1[i],nums2[j]});
            }
        }
        sort(all.begin(), all.end(), cmp);
        while (all.size() > k)
            all.pop_back();
        return all;
    }
};