CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

    • 队列理论基础
    • 用队列实现栈
    • 滑动窗口的平均值
    • 最近请求次数
    • 单调队列问题

    • 堆-优先级队列

      • 堆理论基础
      • 手写堆
      • 数据流的第 K 大数值
      • 数组中的第k大的数字
      • 前 K 个高频元素
      • 最小的 k 个数
      • 和最小的 k 个数对
        • 📃 题目描述
        • 🔔 解题思路
        • 💥 复杂度分析
      • 数据流中的中位数:对顶堆问题
  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 队列
  • 堆-优先级队列
小牛肉
2022-03-20
目录

和最小的 k 个数对

# 📃 题目描述

题目链接:

  • 373. 查找和最小的 K 对数字 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
  • 剑指 Offer II 061. 和最小的 k 个数对 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)

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

# 🔔 解题思路

帮助理解:我们需要的其实是堆底部的数据,这道题我们的目标是较小的数字,大根堆的底部就是较小的数字,所以这题用大根堆。

用最大堆来存储这 k 个和最小的数对。逐一将 m×n 个数对添加到最大堆中。

  • 当堆中的数对的数目小于 k 时,直接将数对添加到堆中
  • 如果堆中已经有k个数对,那么先要比较待添加的数对之和及堆顶的数对之和(也是堆中最大的数对之和):
    • 如果待添加的数对之和 >= 堆顶的数对之和,那么堆中的 k 个数对之和都小于或等于待添加的数对之和,因此待添加的数对可以忽略。
    • 如果待添加的数对之和 < 堆顶的数对之和,那么删除堆顶的数对,并将待添加的数对添加到堆中,这样可以确保堆中存储的是和最小的k个数对。每次都是将待添加的数对与堆中和最大的数对进行比较,而这也是用最大堆的原因。

接下来考虑如何优化。题目给出的条件是输入的两个数组都是递增排序的,这个特性我们还没有用到。

如果从第1个数组中选出第 k+1 个数字和第2个数组中的某个数字组成数对 p,那么该数对之和一定不是和最小的 k 个数对中的一个,因为第 1 个数组中的前 k 个数字和第 2 个数组中的同一个数字组成的 k 个数对之和一定是小于数对 p 之和的。

因此,不管输入的数组nums1有多长,最多只需要考虑前 k 个数字。同理,不管输入的数组nums2有多长,最多也只需要考虑前 k 个数字。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();

        // 根据(u,v)的和构建大根堆
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (o1, o2) -> (o2[0] + o2[1] - o1[0] - o1[1])
        );

        for (int i = 0; i < Math.min(k, nums1.length); i ++) {
            for (int j = 0; j < Math.min(k, nums2.length); j ++) {
                if (maxHeap.size() < k) {
                    maxHeap.offer(new int[] {nums1[i], nums2[j]});
                }
                else {
                    if (nums1[i] + nums2[j] < maxHeap.peek()[0] + maxHeap.peek()[1]) {
                        maxHeap.poll();
                        maxHeap.offer(new int[] {nums1[i], nums2[j]});
                    }
                }
            }
        }

        while (!maxHeap.isEmpty()) {
            int[] temp = maxHeap.poll();
            res.add(Arrays.asList(temp[0], temp[1]));
        }


        return res;
    }
}

# 💥 复杂度分析

  • 空间复杂度:O(k)。优先队列中最多只保存 k 个元素
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
最小的 k 个数
数据流中的中位数:对顶堆问题

← 最小的 k 个数 数据流中的中位数:对顶堆问题→

最近更新
01
我掏出这个多线程轮子,面试官直接全体起立
04-13
02
面试官问你有其他 Offer 吗,该怎样回答
04-10
03
天不生陈志龙,职场万古如长夜
04-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式