当前位置: 首页 > news >正文

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 大和 定义为&#xff1a;可以获得的第 k 个 最大 子序列和&#xff08;子序列和允许出现重复&#xff09; 返回数组的 第 k 大和 。 子序列是一个可以由其他数…...

基于微信小程序的付费自习室

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

纪念在CSDN的2048天

时间真快&#xff5e;...

云原生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保姆级教程五:视图组件

&#x1f482; 个人主页:pp不会算法v &#x1f91f; 版权: 本文由【pp不会算法v】原创、在CSDN首发、需要转载请联系博主 &#x1f4ac; 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦 QML系列教程 QML教程一&#xff1a;布局组件 文章目录 列表视图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清理软件&#xff0c;它的设计理念是提供多个模块&#xff0c;包括垃圾清理、安全保护、速度优化、应用程序管理和文档管理粉碎等&#xff0c;以满足用户的不同需求。软件的界面简洁直观&#xff0c;让用户能够轻松进行日常的清理操作。 使用C…...

芯驰D9评测(3)--建立开发环境

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

阿里云服务器IP地址查询方法(公网IP和私网IP)

阿里云服务器IP地址在哪查看&#xff1f;在云服务器ECS管理控制台即可查看&#xff0c;阿里云服务器IP地址包括公网IP和私有IP地址&#xff0c;阿里云百科分享阿里云服务器IP地址查询方法&#xff1a; 目录 阿里云服务器IP地址查询 阿里云服务器IP地址查询 1、登录到阿里云服…...

第47节——使用bindActionCreators封装actions模块

一、什么是action creators 1、概念 在Redux中&#xff0c;Action Creators是一种函数&#xff0c;它用于创建一个描述应用程序状态变化的action对象。Action对象是一个普通JavaScript对象&#xff0c;它包含一个描述action类型的字符串属性&#xff08;通常称为“type”&…...

QT、c/c++通过宏自动判断平台

QT、c/c通过宏自动判断平台 Chapter1 QT、c/c通过宏自动判断平台 Chapter1 QT、c/c通过宏自动判断平台 原文链接&#xff1a;https://blog.csdn.net/qq_32348883/article/details/123063830 背景 为了更好的进行跨平台移植、编译、调试。 具体操作 宏操作 #ifdef _WIN32//d…...

对比表:阿里云轻量应用服务器和服务器性能差异

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

中国1km分辨率月最低温和最高温度数据集(1901-2020)

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

EasyX图形库note4,动画及键盘交互

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

C++设计模式-原型(Prototype)

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

[补题记录] Atcoder Beginner Contest 322(E)

URL&#xff1a;https://atcoder.jp/contests/abc322 目录 E Probelm/题意 Thought/思路 Code/代码 E Probelm/题意 有 N 个改进计划&#xff0c;每个计划可以执行一次&#xff1b;有 K 个参数&#xff0c;每个计划可以将所有参数提升固定值&#xff0c;即计划 i 可以为第…...

目标检测算法改进系列之Backbone替换为FocalNet

FocalNet 近些年&#xff0c;Transformers在自然语言处理、图像分类、目标检测和图像分割上均取得了较大的成功&#xff0c;归根结底是自注意力&#xff08;SA &#xff1a;self-attention&#xff09;起到了关键性的作用&#xff0c;因此能够支持输入信息的全局交互。但是由于…...

buuctf-[BSidesCF 2020]Had a bad day 文件包含

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

Elasticsearch:什么时候应该考虑在 Elasticsearch 中添加协调节点?

仅协调节点&#xff08;coordinating only nodes&#xff09;充当智能负载均衡器。 仅协调节点的这种特殊角色通过减轻数据和主节点的协调责任&#xff0c;为广泛的集群提供了优势。 加入集群后&#xff0c;这些节点与任何其他节点类似&#xff0c;都会获取完整的集群状态&…...

Dubbo3应用开发—Dubbo注册中心引言

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

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...