专栏首页架构说每日打卡 373. 查找和最小的K对数字

每日打卡 373. 查找和最小的K对数字

“Yesterday I was clever, so I wanted to change the world. Today I am wise, so I am changing Myself."

昨天的我聪明,想去改变这个世界。今天的我智慧,正在改进自我。

一、描述

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.

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
 
定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2。
找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]] 
Explanation: 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]

思考 60秒 。。。

思考 60秒 。。

这个题目试着这里开始入手

算法五个重要的特征:

  • 输入项,输出项(题目已经给了)
  • 可行性(复杂问题转化成熟悉子问题)
  • 有穷性(在算法描述体现)
  • 确切性(在算法描述体现)

二、思路

最迷惑地方 pair (u,v)

题目告诉你 2个有序数组,求top k 不是 从2个有序数组获取一个记录就可以了。

想想暴力破解,是全部组合**(uk,vk)** ,我们可以暴力枚举全部的n1*n2对数字

熟悉子问题:

问:和最小的 k对数字,一定来两个以升序排列的整形数组,前面k个吗?

答:

最好情况k=1,最坏情况 k=n+m

k不一定小于 n或者m Input: nums1 = [10,20,30], nums2 = [1,2], k = 3

问:和最小的 k对数字,移动多少个可能 n+m

回答:错误,n*m个 。下图。

必须全部遍历,不是通过公式直接定位的。

问:在不全部遍历情况下,如何求top k

原问题转换成在n1个升序队列中,查找最小的前K对数字

  • 转换过程 k --->(n,m) -->n*m --->k 成在n1个升序队列中,查找最小的前K对数字

描述

  1. 一次性构造小顶堆
  2. 循环k次

测试bug

一个小错误:你发现了吗?

for (int i=k;i>0 && !priorityQueue.empty();k--) 有可能是死循环。i根本没有发送变化

三、代码

  • 放轻松,虽然是c++实现,拒绝奇技淫巧,通俗易懂。
// @lc code=start
class Solution
{
public:
    //找到和最小的 k 对数字
    //Solution1 找到全部组合n*m,然后排序。
    //Solution2 利用堆,在不枚举出全部数对的情况下
    //原问题转换成在n1个升序队列中,查找最小的前K对数字
    //Time  O(KlogN)
    vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2, int k)
    {
        int rows = nums1.size();
        int cols = nums2.size();
        vector<vector<int>> topK; //输出结果
        if (rows == 0 || cols == 0)
            return topK;

        // auto cmp = [&nums1, &nums2](pair<int, int> &a, pair<int, int> &b) {
        //     return (nums1[a.first] + nums2[b.second]) > (nums1[a.first] + nums2[b.second]);
        // }; //(3,(0,0)) (9,(1,0))  构造小顶堆

        auto cmp = [&nums1, &nums2](const pair<int, int> &a, const pair<int, int> &b) { return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second]; };

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> priorityQueue(cmp);

        //假设nums1每个元素和 有序数组nums1相加后,产生n个有序数组.
        //{3,5.7}
        //{9.11.13}
        //{13,15,17}
        //然后组成n×m升序矩阵。

        //插入n个有序数组中的一个元素
        for (int i = 0; i < rows; i++)
        {
            priorityQueue.emplace(i, 0);
        }

        //找到和最小的 k 对数字 
        while (k > 0 && !priorityQueue.empty())
        {
            k--; //每次比较获取最小的一个元素,类比合并2个有序链表。
            pair<int, int> temp = priorityQueue.top();
            priorityQueue.pop(); //获取一个记录
            cout << nums1[temp.first] << ":" << nums2[temp.second] << endl;
            if (temp.second + 1 < cols)
            {
                cout << nums1[temp.first] << " insert " << nums2[temp.second + 1] << endl;
                priorityQueue.emplace(temp.first, temp.second + 1); //列+1
            }

            vector<int> item;
            item.push_back(nums1[temp.first]);
            item.push_back(nums2[temp.second]);

            topK.push_back(item);
        }

        return topK;
    }
};
  • golang

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • c++系列之二 指向成员函数的指针(烧脑)

    这是一篇翻译的文章,原文详细解释了C++中指向成员函数的指针,因为带有“教程”一词,所以比较通俗易懂。为了使文章读起来通俗有趣,翻译君并未一字一句一板一眼地翻译...

    程序员小王
  • leetcode第513题-找树左下角的值

    Given a binary tree, find the left most value in the last row of the tree.

    程序员小王
  • stl map key 可以被修改吗?

    stl map key 可以被修改吗 image.png 不可以修改 map节点存储key是const std::pair<const char, int>...

    程序员小王
  • 【leetcode刷题】T43-两个数组的交集

    Given two arrays, write a function to compute their intersection.

    木又AI帮
  • Leetcode No.4 寻找两个正序数组的中位数

    请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

    week
  • 力扣LeetCode,两个数组的交集

    别先生
  • LeetCode 349. Intersection of Two Arrays题目代码代码

    样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].

    desperate633
  • Leetcode#88. Merge Sorted Array(合并两个有序数组)

    给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

    武培轩
  • leetcode 4 Median of Two Sorted Arrays

    @坤的
  • 【每天一道编程系列-2018.2.18】(Ans)

    There are two sorted arrays nums1 and nums2 of size m and n respectively. Find ...

    yesr

扫码关注云+社区

领取腾讯云代金券