C++二分查找算法:有序矩阵中的第 k 个最小数组和

本文涉及的基础知识点

二分查找算法合集

本题的简化

C++二分查找算法:查找和最小的 K 对数字 十分接近m恒等于2

题目

给你一个 m * n 的矩阵 mat,以及一个整数 k ,矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
示例 1:
输入:mat = [[1,3,11],[2,4,6]], k = 5
输出:7
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。
示例 2:
输入:mat = [[1,3,11],[2,4,6]], k = 9
输出:17
示例 3:
输入:mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出:9
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。
示例 4:
输入:mat = [[1,1,10],[2,2,9]], k = 7
输出:12
参数范围
m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组

分析

时间复杂度

O(mlog(500040)n+mkn)。GetLessKSum被调用m次,GetLessEqualSumNum共被调用mlog(500040)次。每次调用GetLessEqualSumNum,for循环共执行m次。
vRet.emplace_back极端情况下,可能被执行k
n次。

主要函数介绍

GetLessKSum两行升序数据的最小k个和
GetLessEqualSumNum两行升序数据和小于等于iSum的组合数量

注意:nums[i]为正数,所以如果pre的数量大于k,只需要保留前k小,其它的被淘汰了。

二分

寻找第一个符合条件的iSum,条件如下:
和小于等于iSum的组合数量大于等于k。

代码

核心代码

class Solution {
public:int kthSmallest(vector<vector<int>>& mat, int k) {m_c = mat.front().size();m_iK = k;vector<int> pre = mat[0];for (int r = 1; r < mat.size(); r++){pre = GetLessKSum(pre, mat[r]);}return pre.back();}vector<int> GetLessKSum(const vector<int>& pre, const vector<int>& cur){int left = 0, right = 5000 * 40;while (right - left > 1){const auto mid = left + (right - left) / 2;if (GetLessEqualSumNum(pre, cur, mid)>= m_iK){right = mid;}else{left = mid;}}vector<int> vRet;for (const auto& pr : pre){for (const auto& cu : cur){if (pr + cu <= right){vRet.emplace_back(pr + cu);}else{break;}}}sort(vRet.begin(), vRet.end());if (vRet.size() > m_iK){vRet.erase(vRet.begin() + m_iK, vRet.end());}return vRet;}int GetLessEqualSumNum(const vector<int>& pre, const vector<int>& cur,int iSum){int iNum = 0;for (const auto& pr : pre){iNum += std::upper_bound(cur.begin(), cur.end(), iSum - pr)- cur.begin();}return iNum;}int m_iK;int m_c;
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
vector<vector> mat;
int k;
int res;
{
Solution slu;
mat = { {1,3,11},{2,4,6} };
k = 5;
res = slu.kthSmallest(mat, k);
Assert(7, res);
}
{
Solution slu;
mat = { {1,3,11},{2,4,6} };
k = 9;
res = slu.kthSmallest(mat, k);
Assert(17, res);
}
{
Solution slu;
mat = { {1,10,10},{1,4,5},{2,3,6} };
k = 7;
res = slu.kthSmallest(mat, k);
Assert(9, res);
}
{
Solution slu;
mat = { {1,1,10},{2,2,9} };
k = 7;
res = slu.kthSmallest(mat, k);
Assert(12, res);
}

//CConsole::Out(res);

}

优化增加结果

vector<int> vRet;for (const auto& pr : pre){for (const auto& cu : cur){if (pr + cu < right){vRet.emplace_back(pr + cu);}else{break;}}}while (vRet.size() < m_iK){vRet.emplace_back(right);}

和小于right的数量<=k,如果不足够,则补right。时间复杂度由O(nk)降低到O(k+n)。

直接使用封装类

namespace NBinarySearch
{template<class INDEX_TYPE,class _Pr>INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE right, _Pr pr){while (right - left > 1){const auto mid = left + (right - left) / 2;if (pr(mid)){right = mid;}else{left = mid;}}return right;}
}class Solution {
public:int kthSmallest(vector<vector<int>>& mat, int k) {m_c = mat.front().size();m_iK = k;vector<int> pre = mat[0];for (int r = 1; r < mat.size(); r++){pre = GetLessKSum(pre, mat[r]);}return pre.back();}vector<int> GetLessKSum(const vector<int>& pre, const vector<int>& cur){auto GetLessEqualSumNum = [&pre, &cur, this](const int iSum)-> bool{int iNum = 0;for (const auto& pr : pre){iNum += std::upper_bound(cur.begin(), cur.end(), iSum - pr) - cur.begin();}return iNum >= m_iK;};const int right = NBinarySearch::FindFrist(0, 5000 * 40, GetLessEqualSumNum);		vector<int> vRet;for (const auto& pr : pre){for (const auto& cu : cur){if (pr + cu < right){vRet.emplace_back(pr + cu);}else{break;}}}while (vRet.size() < m_iK){vRet.emplace_back(right);}sort(vRet.begin(), vRet.end());if (vRet.size() > m_iK){vRet.erase(vRet.begin() + m_iK, vRet.end());}return vRet;}int GetLessEqualSumNum(const vector<int>& pre, const vector<int>& cur,int iSum){int iNum = 0;for (const auto& pr : pre){iNum += std::upper_bound(cur.begin(), cur.end(), iSum - pr)- cur.begin();}return iNum;}int m_iK;int m_c;
};

2023年3月暴力版

直接保留前k个。时间复杂度:O(mknlogk)
class Solution {
public:
int kthSmallest(vector<vector>& mat, int k) {
m_r = mat.size();
m_c = mat[0].size();
std::priority_queue pre;
pre.push(0);
for (int r = 0; r < mat.size(); r++)
{
std::priority_queue dp;
while (pre.size())
{
int t = pre.top();
pre.pop();
for (int c = 0; c < m_c; c++)
{
dp.push(mat[r][c] + t);
if (dp.size() > k)
{
dp.pop();
}
}
}
pre.swap(dp);
}
return pre.top();
}
int m_r, m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨子曰:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:

VS2022 C++17

本文涉及的基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/198245.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

mac控制台命令小技巧

shigen日更文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 hello伙伴们&#xff0c;作为忠实的mac骨灰级别的粉丝&#xff0c;它真的给我带来了很多效率上的提升。那作为接…

计算机网络的体系结构

目录 一. 计算机体系结构的形成二. 协议与层次划分2.1 数据传输过程2.2 什么是网络协议2.3 网络协议的三要素2.4 协议有两种形式2.4 各层协议2.5 什么是复用和分用 \quad 一. 计算机体系结构的形成 \quad 计算机网络是一个非常复杂的系统, 相互通信的两个计算机系统必须高度协调…

vim指令

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大二&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;熟练掌握vim&#xff0c;并且能用vim敲出简单的代…

如何看待人工智能行业发展

随着人工智能技术的飞速发展&#xff0c;这个领域的就业前景也日益广阔。人工智能在各行各业都有广泛的应用&#xff0c;包括医疗、金融、制造业、教育等。因此&#xff0c;对于想要追求高薪、高技能职业的人来说&#xff0c;学习人工智能是一个非常有前景的选择。 首先&#x…

高性能音乐流媒体服务Diosic

什么是 Diosic ? Diosic 是一个开源的基于网络的音乐收集服务器和流媒体。主要适合需要部署在硬件规格不高的服务器上的用户。Diosic 是使用 Rust 开发的&#xff0c;具有低内存使用率和高性能以及用于流媒体音乐的非常干净的界面。 安装 在群晖上以 Docker 方式安装。 在注…

程序员告诉你:人工智能是什么?

随着科技的快速发展&#xff0c;人工智能这个词汇已经逐渐融入了我们的日常生活。然而&#xff0c;对于大多数人来说&#xff0c;人工智能仍然是一个相对模糊的概念。 首先&#xff0c;让我们从人工智能的定义开始。人工智能是一种模拟人类智能的技术&#xff0c;它涵盖了多个领…

【Java程序员面试专栏 专业技能篇】Java SE核心面试指引(一):基础知识考察

关于Java SE部分的核心知识进行一网打尽,包括四部分:基础知识考察、面向对象思想、核心机制策略、Java新特性,通过一篇文章串联面试重点,并且帮助加强日常基础知识的理解,全局思维导图如下所示 本篇Blog为第一部分:基础知识考察,子节点表示追问或同级提问 基本概念 …

Ubuntu20.04 安装微信 【wine方式安装】推荐

安装步骤: 第一步:安装 WineHQ 安装包 先安装wine,根据官网指导安装即可。下载 - WineHQ Wikihttps://wiki.winehq.org/Download_zhcn 如果您之前安装过来自其他仓库的 Wine 安装包,请在尝试安装 WineHQ 安装包之前删除它及依赖它的所有安装包(如:wine-mono、wine-gec…

Clickhouse初认识

技术主题-clickhouse 一什么是clickHouse 1&#xff09;本质上就是一款数据库管理系统&#xff0c;能提供海量数据的存储和检索 2&#xff09;基于列存储&#xff0c;数据是按照列进行存储的&#xff08;数据格式一样&#xff0c;方便进行压缩&#xff09; 3&#xff09;具备…

【Flink】窗口(Window)

窗口理解 窗口&#xff08;Window&#xff09;是处理无界流的关键所在。窗口可以将数据流装入大小有限的“桶”中&#xff0c;再对每个“桶”加以处理。 本文的重心将放在 Flink 如何进行窗口操作以及开发者如何尽可能地利用 Flink 所提供的功能。 对窗口的正确理解&#xff…

nn.KLDivLoss,nn.CrossEntropyLoss,nn.MSELoss,Focal_Loss

KL loss&#xff1a;https://blog.csdn.net/qq_50001789/article/details/128974654 https://pytorch.org/docs/stable/nn.html 1. nn.L1Loss 1.1 公式 L1Loss: 计算预测 x和 目标y之间的平均绝对值误差MAE, 即L1损失&#xff1a; l o s s 1 n ∑ i 1 , . . . n ∣ x i…

【C++入门到精通】新的类功能 | 可变参数模板 C++11 [ C++入门 ]

阅读导航 引言一、新的类功能1. 默认成员函数2. 类成员变量初始化3. 强制生成默认函数的关键字default4. 禁止生成默认函数的关键字delete5. override 和 final&#xff08;1&#xff09;override&#xff08;2&#xff09;final 二、可变参数模板递归函数方式展开参数包逗号表…

读像火箭科学家一样思考笔记03_第一性原理(上)

1. 思维的两种障碍 1.1. 为什么知识会成为一种缺陷而非一种美德 1.1.1. 知识是一种美德 1.1.2. 知识同样的特质也会把它变成一种缺点 1.1.3. 知识确实是个好东西&#xff0c;但知识的作用应该是给人们提供信息&#xff0c;而不是起约束作用 1.1.4. 知识应该启发智慧&#…

Git精讲

Git基本操作 创建Git本地仓库 git initgit clone 配置Git git config [--global] user.name "Your Name" git config [--global] user.email "emailexample.com"–global是一个可选项。如果使用了该选项&#xff0c;表示这台机器上所有的Git仓库都会使…

6 Redis的慢查询配置

1、redis的命令执行流程 redis的慢查询只针对步骤3 默认情况下&#xff0c;慢查询的阈值是10ms 在配置文件中进行配置 //这个参数的单位为微秒 //如果将这个值设置为负数&#xff0c;则会禁用慢日志功能 //如果将其设置为0&#xff0c;则会强制记录每个命令 slowlog-log-slow…

【C++历练之路】list的重要接口||底层逻辑的三个封装以及模拟实现

W...Y的主页 &#x1f60a; 代码仓库分享&#x1f495; &#x1f354;前言&#xff1a; 在C的世界中&#xff0c;有一种数据结构&#xff0c;它不仅像一个神奇的瑰宝匣&#xff0c;还像一位能够在数据的海洋中航行的智慧舵手。这就是C中的list&#xff0c;一个引人入胜的工具…

立仪科技光谱共焦在半导体领域的应用

半导体技术在近年来以极快的速度发展&#xff0c;对质量和精密度的要求也不断提升。在这样的背景下&#xff0c;用于材料与设备研究的先进检测技术如光谱共焦成像将自然地找到一席之地。下面我们将详细探讨一下光谱共焦在半导体领域中的应用。 光谱共焦技术&#xff0c;通过在细…

【DevOps】Git 图文详解(四):Git 使用入门

Git 图文详解&#xff08;四&#xff09;&#xff1a;Git 使用入门 1.创建仓库2.暂存区 add3.提交 commit 记录4.Git 的 “指针” 引用5.提交的唯一标识 id&#xff0c;HEAD~n 是什么意思&#xff1f;6.比较 diff 1.创建仓库 创建本地仓库的方法有两种&#xff1a; 一种是创建…

MongoDB之索引和聚合

文章目录 一、索引1、说明2、原理3、相关操作3.1、创建索引3.2、查看集合索引3.3、查看集合索引大小3.4、删除集合所有索引&#xff08;不包含_id索引&#xff09;3.5、删除集合指定索引 4、复合索引 二、聚合1、说明2、使用 总结 一、索引 1、说明 索引通常能够极大的提高查…

CSS的选择器(一篇文章齐全)

目录 Day26&#xff1a;CSS的选择器 1、CSS的引入方式 2、CSS的选择器 2.1 基本选择器​编辑 2.2 组合选择器 2.3 属性选择器 2.4 伪类选择器 2.5 样式继承 2.6 选择器优先级 3、CSS的属性操作 3.1 文本属性 3.2 背景属性 3.3 边框属性 3.4 列表属性 3.5 dispal…