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集群的健康情况,动态的上线或者下线服务。让我…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...
数据库——redis
一、Redis 介绍 1. 概述 Redis(Remote Dictionary Server)是一个开源的、高性能的内存键值数据库系统,具有以下核心特点: 内存存储架构:数据主要存储在内存中,提供微秒级的读写响应 多数据结构支持&…...