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

蔚落 2022-06-07 02:47 125阅读 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;
        }
    };