首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:查找和最小的 K 对数字

#yyds干货盘点# LeetCode程序员面试金典:查找和最小的 K 对数字

时间:2023-08-13 14:01:00浏览次数:43  
标签:yyds idxPair pq int 金典 LeetCode new nums1 nums2

1.简述:

给定两个以 非递减顺序排列 的整数数组 和  , 以及一个整数  。nums1nums2k

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

请找到和最小的  个数对 , 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]

2.代码实现:

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2)->{
            return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
        });
        List<List<Integer>> ans = new ArrayList<>();
        int m = nums1.length;
        int n = nums2.length;
        for (int i = 0; i < Math.min(m, k); i++) {
            pq.offer(new int[]{i,0});
        }
        while (k-- > 0 && !pq.isEmpty()) {
            int[] idxPair = pq.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            ans.add(list);
            if (idxPair[1] + 1 < n) {
                pq.offer(new int[]{idxPair[0], idxPair[1] + 1});
            }
        }
        
        return ans;
    }
}

标签:yyds,idxPair,pq,int,金典,LeetCode,new,nums1,nums2
From: https://blog.51cto.com/u_15488507/7066978

相关文章

  • LeetCode 377.组和总和IV
    1.题目:给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合32位整数范围。 https://leetcode.cn/problems/combination-sum-iv/description/示例1:输入:nums=[1,2,3],targ......
  • LeetCode 518.零钱兑换II
    1.题目:给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。假设每一种面额的硬币有无限个。 题目数据保证结果符合32位带符号整数。 https://leetcode.cn/......
  • LeetCode 474.一和零
    1.题目:给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。 https://leetcode.cn/problems/ones-and-zeroes/d......
  • #yyds干货盘点# LeetCode程序员面试金典:最短回文串
    题目:给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例1:输入:s="aacecaaa"输出:"aaacecaaa"示例2:输入:s="abcd"输出:"dcbabcd"代码实现:classSolution{publicStringshortestPalindrome(Strings){......
  • #yyds干货盘点# LeetCode程序员面试金典:超级次方
    1.简述:你的任务是计算  对  取模, 是一个正整数, 是一个非常大的正整数且会以数组形式给出。ab1337ab 示例1:输入:a=2,b=[3]输出:8示例2:输入:a=2,b=[1,0]输出:1024示例3:输入:a=1,b=[4,3,3,8,5,2]输出:1示例4:输入:a=2147483647,b=[2,0,0]输出:11982.代码实......
  • # yyds干货盘点 #通过pandas读取列的数据怎么把一列中的负数全部转为正数?
    大家好,我是皮皮。一、前言前几天在Python最强王者群【wen】问了一个pandas数据处理的问题,一起来看看吧。二、实现过程这里【隔壁......
  • #yyds干货盘点# LeetCode程序员面试金典:打家劫舍 II
    题目:你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存放金......
  • #yyds干货盘点# LeetCode程序员面试金典:两整数之和
    1.简述:给你两个整数 和 ,不使用 运算符  和  ,计算并返回两整数之和。ab+- 示例1:输入:a=1,b=2输出:3示例2:输入:a=2,b=3输出:52.代码实现:classSolution{publicintgetSum(inta,intb){while(b!=0){intcarry=(a&b)<<1;......
  • LeetCode 494.目标和
    1.题目:https://leetcode.cn/problems/target-sum/description/给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :例如,nums=[2,1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后......
  • # yyds干货盘点 # 盘点一个dataframe读取csv文件失败的问题
    大家好,我是皮皮。一、前言前几天在Python钻石群【心田有垢生荒草】问了一个Pandas数据处理的问题,一起来看看吧。大佬们求教个方法 现在有个数据量很大的dataframe 要吐csv格式 但结果总是串行 加了encoding='utf-8'还是没解决 还有其他方法么?下图是他提供的图片:二、实现......