查找和最小的k对数字

雨点打透心脏的1/2处 2022-10-22 04:20 132阅读 0赞

### 查找和最小的k对数字 ###

*  查找和最小的k对数字

# 查找和最小的k对数字 #

LeetCode373： 链接：[查找和最小的k对数字][k]

题目描述：  
373. 查找和最小的K对数字  
给定两个以升序排列的整形数组 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 对数：  
> \[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  
> 输出: \[1,1\],\[1,1\]  
> 解释: 返回序列中的前 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\]  
> 解释: 也可能序列中所有的数对都被返回:\[1,3\],\[2,3\]

思路：  
定义一个比较器，通过两个数的和来比较；  
将两个数组，按照排列组合的方式凑成（nums1.length \* nums2.length）对，放在ArrayList中。建立一个小堆，然后将其放在堆中，然后将前k个最小的从堆中拿出来。  
（当然也可以建k个大小的堆，然后依次比较后面的元素，是否需要插入堆中，最后从堆中取出）。

class Solution { 
        static class com implements Comparator<ArrayList<Integer>> { 
    
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { 
                int x = o1.get(0) + o1.get(1);
                int y = o2.get(0) + o2.get(1);
                return x - y;
            }
        }
    
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { 
            List<List<Integer>> list = new ArrayList<>();
            for (int i : nums1) { 
                for (int e : nums2) { 
                    List<Integer> row = new ArrayList<>();
                    row.add(i);
                    row.add(e);
                    list.add(row);
                }
            }
            Comparator comparator = new com();
            Queue<List<Integer>> queue = new PriorityQueue<>(comparator);
    
            for (int i = 0; i < list.size(); i++) { 
                queue.add(list.get(i));
            }
            list.clear();
            while (k > 0 && !queue.isEmpty()) { 
                list.add(queue.remove());
                k--;
            }
            return list;
        }
    }

虽然这种方法的效率不是很高，但是能做出来也是挺好的，后期学会更简单的方法了，我会去修改的，哈哈！![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

[k]: https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/b220e0c79db74a2a989830f1eaab27c0.png