1.7. 找出数组的第 K 大和原理及C++实现
题目
给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。
数组的 第 k 大和 定义为:可以获得的第 k 个 最大 子序列和(子序列和允许出现重复)
返回数组的 第 k 大和 。
子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组,且派生过程不改变剩余元素的顺序。
注意:空子序列的和视作 0 。
nums的长度为[1,100000],nums[i]取值[-10^9,10^9]。
1 <= k <= min(2000, 2n)
时间复杂度
O(nlogn)+O(klogn)。预处理,排序的时间复杂度为O(nlogn);出队入队的时间复杂度为O(klogk)
nums[i]全部是正数,求k大组合和
先按升序排序。用状态压缩来表示系列,如果选取了nums[0],则mask |= 1;如果选取了nums[1],则mask|=2;如果选取了nums[2],则mask|=4;如果选取了nums[3],则mask|=8。
只有一个数 | ||||
1(二进制1) | 0(0) | |||
只有两个数 | ||||
3(11) | 2(10) | 0(00) | ||
1(01) | ||||
只有三个数 | ||||
7(111) | 6(110) | 4(100) | 0(000) | |
2(010) | ||||
5(101) | 1(001) | |||
3(011) | ||||
只有4个数 | ||||
15(1111) | 1110 | 1100 | 1000 | 0000 |
0100 | ||||
1010 | 0010 | |||
0110 | ||||
1101 | 1001 | 0001 | ||
0101 | ||||
1011 | 0011 | |||
0111 |
规律:
规律一:上表中任何数据都小或等于同行前一列。第0列转化一个数,其它列转化两个数。第i列转化方式:a,从系列中删除nums[i]。b,从序列中删除nums[i],增加nums[i-1]。nums[i]大于等于0,所以a方式一定变小或不变;nums[i]>=nums[i-1],b方式也变小或不变。
规律二:第i(从0开始)列,从低到高,第i-1位为0,比i-1高的位全位1,比i-1位低的枚举各种可能。前面是n1个1,中间是0,最后是n2位有2^n2种可能。下一列是n1-1个1,中间是0,最后有n2+1位,2^(n2+1)种可能。去掉重复的首位尾位,就是10变成00和01,分别对应第一点的a,b两种方式。
规律三:第i列一定存在nums[i],因为之前依次删除nums[0]…nums[i-1],没删除过nums[i]。由规律二可以得出一定不存在nums[i-1]。
推论:
由规律一可得,第k大一定是前k-1的a方式或b方式。也就是队列的中元素数是O(k),队列中只需要存在前k-1大的a方式和b方式。
负数处理
假定存在负数,其绝对值为x。任意一个不包括-x的子系列,其和为s,则选取x,其和为s-x。把-x变成x,则不选取x和选取x,分别为s,s+x。我把-x转成x,再对任意序列和减去-x。就等价了。通俗的说,选则-x,变成不选;不选,变成选择x。
负数转为正数之前,计算最大值:所有非负数之和。
负数转为正数之后,计算最大值:所有非负数之和+所有负数的绝对值-所有负数的绝对值=所有非负数之和。
核心代码
class Solution {
public:
long long kSum(vector<int>& nums, int k) {
long long llMax = 0;
for (auto& n : nums)
{
if (n < 0)
{
n *= -1;
}
else
{
llMax += n;
}
}
sort(nums.begin(), nums.end());
std::priority_queue<std::pair<long long, int>> que;
que.emplace(llMax, 0);
while (--k)
{
auto [llSum, i] = que.top();
que.pop();
if (i >= nums.size())
{
continue;
}
que.emplace(llSum - nums[i], i + 1);
if (i > 0)
{
que.emplace(llSum - nums[i]+nums[i-1], i + 1);
}
}
return que.top().first;
}
};
测试用例
int main()
{
vector<int> nums = { 2,4,-2 };
//vector<int> nums = { 6, 3, 6, 1, 0, 8, 0, 6, 6 };
//vector<int> nums = { 1,0,0,2,0 };
auto res = Solution().kSum(nums, 5);
CConsole::Out(res);
}
其它
视频课程
如果你觉得复杂,想从简单的算法开始,可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17
相关下载
doc版文档,排版好
https://download.csdn.net/download/he_zhidan/88348653
相关文章:
1.7. 找出数组的第 K 大和原理及C++实现
题目 给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。 数组的 第 k 大和 定义为:可以获得的第 k 个 最大 子序列和(子序列和允许出现重复) 返回数组的 第 k 大和 。 子序列是一个可以由其他数…...

基于微信小程序的付费自习室
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 文章目录 1 简介2 技术栈3 需求分析3.1用户需求分析3.1.1 学生用户3.1.3 管理员用户 4 数据库设计4.4.1 E…...

纪念在CSDN的2048天
时间真快~...

云原生Kubernetes:简化K8S应用部署工具Helm
目录 一、理论 1.HELM 2.部署HELM2 3.部署HELM3 二、实验 1.部署 HELM2 2.部署HELM3 三、问题 1.api版本过期 2.helm初始化报错 3.pod状态为ImagePullBackOff 4.helm 命令显示 no repositories to show 的错误 5.Helm安装报错 6.git命令报错 7.CentOS 7 下git c…...

qml保姆级教程五:视图组件
💂 个人主页:pp不会算法v 🤟 版权: 本文由【pp不会算法v】原创、在CSDN首发、需要转载请联系博主 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦 QML系列教程 QML教程一:布局组件 文章目录 列表视图ListVi…...
2310d编译不过
struct A {this(int[] data) safe { a data; }int[] a; }void main() safe {int[3] test [1, 2, 3];A a A(test); }应该给data参数加上return scope.或让构造器为模板参数来推导,否则,构造器可以把栈分配切片赋值给全局变量....

CleanMyMac X4.14.1最新版本下载
CleanMyMac X是一个功能强大的Mac清理软件,它的设计理念是提供多个模块,包括垃圾清理、安全保护、速度优化、应用程序管理和文档管理粉碎等,以满足用户的不同需求。软件的界面简洁直观,让用户能够轻松进行日常的清理操作。 使用C…...

芯驰D9评测(3)--建立开发环境
1. 建立交叉编译链接环境 官网下载的SDK包中就有交叉工具链,米尔提供的这个 SDK 中除了包含各种源代码外还提供了必要的交叉工具链,可以直接用于编译应用程序等。 用户可以直接使用次交叉编译工具链来建立一个独立的开发环境,可单独编译…...

阿里云服务器IP地址查询方法(公网IP和私网IP)
阿里云服务器IP地址在哪查看?在云服务器ECS管理控制台即可查看,阿里云服务器IP地址包括公网IP和私有IP地址,阿里云百科分享阿里云服务器IP地址查询方法: 目录 阿里云服务器IP地址查询 阿里云服务器IP地址查询 1、登录到阿里云服…...
第47节——使用bindActionCreators封装actions模块
一、什么是action creators 1、概念 在Redux中,Action Creators是一种函数,它用于创建一个描述应用程序状态变化的action对象。Action对象是一个普通JavaScript对象,它包含一个描述action类型的字符串属性(通常称为“type”&…...
QT、c/c++通过宏自动判断平台
QT、c/c通过宏自动判断平台 Chapter1 QT、c/c通过宏自动判断平台 Chapter1 QT、c/c通过宏自动判断平台 原文链接:https://blog.csdn.net/qq_32348883/article/details/123063830 背景 为了更好的进行跨平台移植、编译、调试。 具体操作 宏操作 #ifdef _WIN32//d…...

对比表:阿里云轻量应用服务器和服务器性能差异
阿里云服务器ECS和轻量应用服务器有什么区别?轻量和ECS优缺点对比,云服务器ECS是明星级云产品,适合企业专业级的使用场景,轻量应用服务器是在ECS的基础上推出的轻量级云服务器,适合个人开发者单机应用访问量不高的网站…...

中国1km分辨率月最低温和最高温度数据集(1901-2020)
简介: 中国1km分辨率月最低温度数据集(1901-2020)是根据CRU发布的全球0.5气候数据集以及WorldClim发布的全球高分辨率气候数据集,通过Delta空间降尺度方案在中国地区降尺度生成的。使用了496个独立气象观测点数据进行验证&#x…...

EasyX图形库note4,动画及键盘交互
大家好,这里是Dark Flame Master,专栏从这篇开始就会变得很有意思,我们可以利用今天所学的只是实现很多功能,同样为之后的更加好玩的内容打下基础,从这届开始将会利用所学的知识制作一些小游戏,废话不多说&…...

C++设计模式-原型(Prototype)
目录 C设计模式-原型(Prototype) 一、意图 二、适用性 三、结构 四、参与者 五、代码 C设计模式-原型(Prototype) 一、意图 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象。 二、适用性 当…...

[补题记录] Atcoder Beginner Contest 322(E)
URL:https://atcoder.jp/contests/abc322 目录 E Probelm/题意 Thought/思路 Code/代码 E Probelm/题意 有 N 个改进计划,每个计划可以执行一次;有 K 个参数,每个计划可以将所有参数提升固定值,即计划 i 可以为第…...

目标检测算法改进系列之Backbone替换为FocalNet
FocalNet 近些年,Transformers在自然语言处理、图像分类、目标检测和图像分割上均取得了较大的成功,归根结底是自注意力(SA :self-attention)起到了关键性的作用,因此能够支持输入信息的全局交互。但是由于…...

buuctf-[BSidesCF 2020]Had a bad day 文件包含
打开环境 就两个按钮,随便按按 url变了 还有 像文件包含,使用php伪协议读取一下,但是发现报错,而且有两个.php,可能是自己会加上php后缀 所以把后缀去掉 /index.php?categoryphp://filter/convert.base64-encode/resourcei…...

Elasticsearch:什么时候应该考虑在 Elasticsearch 中添加协调节点?
仅协调节点(coordinating only nodes)充当智能负载均衡器。 仅协调节点的这种特殊角色通过减轻数据和主节点的协调责任,为广泛的集群提供了优势。 加入集群后,这些节点与任何其他节点类似,都会获取完整的集群状态&…...

Dubbo3应用开发—Dubbo注册中心引言
Dubbo注册中心引言 什么是Dubbo注册中心 Dubbo的注册中心,是Dubbo服务治理的⼀个重要的概念,他主要用于 RPC服务集群实例的管理。 注册中心的运行流程 使用注册中心的好处 可以有效的管理RPC集群的健康情况,动态的上线或者下线服务。让我…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...

《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...

基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...

Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...