leetcode373-查找和最小的K对数字

原题

给定两个以升序排列的整形数组 nums1nums2, 以及一个整数 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]

解法

思想

可以把所有的二元组插入堆中,通过自定义的比较器来获取topk。

代码

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<List<Integer>> queue = new PriorityQueue<>(
            new Comparator<List<Integer>>() {
            public int compare(List<Integer> o1, List<Integer> o2) {
                int ans = 0;
                for(Integer i:o1)
                    ans+=i;
                for(Integer i:o2)
                    ans-=i;
                return ans;
            }
        });
        for(int i:nums1){
            for(int j:nums2){
                List<Integer> list = new ArrayList<>();
                list.add(i);
                list.add(j);
                queue.add(list);
            }
        }
        for(int i = 0;i<k;i++){
            if(queue.isEmpty()) break;
            ans.add(queue.poll());
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode373-%e6%9f%a5%e6%89%be%e5%92%8c%e6%9c%80%e5%b0%8f%e7%9a%84k%e5%af%b9%e6%95%b0%e5%ad%97/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月13日
下一篇 2020年2月13日

相关推荐

  • leetcode599-两个列表的最小索引总和

    原题 假设Andy和Doris想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果…

    算法 2019年12月22日
    0120
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0140
  • leetcode9-回文数

    原题 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: fa…

    算法 2020年2月28日
    0120
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0100
  • leetcode974-和可被K整除的子数组

    原题 给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。 示例: 输入: A = [4,5,0,-2,-3,1], K = 5 输出: 7 解释: …

    算法 2020年5月27日
    0170
  • leetcode49-字母异位词分组

    原题 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat",…

    算法 2019年12月25日
    0110
  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示: 你可以假定这些字符串都是格式良好的: 字符串非空 字符…

    算法 2020年1月28日
    02260
  • leetcode376-摆动序列

    原题 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,…

    算法 2020年2月18日
    0110
  • leetcode160-相交链表

    原题 编写一个程序,找到两个单链表相交的起始节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入: intersectVal = 8, listA = [4,1,…

    2019年12月14日
    090
  • leetcode322-零钱兑换

    原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1…

    算法 2020年3月8日
    0150

发表回复

登录后才能评论