当前位置:网站首页>LeetCode简单题之找到和最大的长度为 K 的子序列
LeetCode简单题之找到和最大的长度为 K 的子序列
2022-07-31 02:56:00 【·星辰大海】
题目
给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ,且这个子序列的 和最大 。
请你返回 任意 一个长度为 k 的整数子序列。
子序列 定义为从一个数组里删除一些元素后,不改变剩下元素的顺序得到的数组。
示例 1:
输入:nums = [2,1,3,3], k = 2
输出:[3,3]
解释:
子序列有最大和:3 + 3 = 6 。
示例 2:
输入:nums = [-1,-2,3,4], k = 3
输出:[-1,3,4]
解释:
子序列有最大和:-1 + 3 + 4 = 6 。
示例 3:
输入:nums = [3,4,3,3], k = 2
输出:[3,4]
解释:
子序列有最大和:3 + 4 = 7 。
另一个可行的子序列为 [4, 3] 。
提示:
1 <= nums.length <= 1000
-10^5 <= nums[i] <= 10 ^5
1 <= k <= nums.length
来源:力扣(LeetCode)
解题思路
这个题所要求的结果数组在原数组中是不需要连续的,这样就大大降低了题目的难度,所以第一步可以先将给定的数组排序,然后取出最大的几个元素和它们的下标,然后在截取符合条件的结果并返回正确的在原数组中的先后顺序。
class Solution:
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
new_nums=sorted(enumerate(nums),key=lambda x:-x[1])
ans=sorted(new_nums[0:k],key=lambda x:x[0])
return [i[1] for i in ans]
当然这道题其实是不需要完全将排序做完的,最好的方法就是用选择排序将符合条件的k个选出来后便不再继续排序。
class Solution:
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
ans=[]
for i in range(k):
MAX,index=-float('inf'),-1
for j in enumerate(nums):
if j[1]!=None:
if j[1]>MAX:
MAX,index=j[1],j[0]
ans.append((index,MAX))
nums[index]=None
return [i[1] for i in sorted(ans)]
边栏推荐
- execsnoop 工具
- CentOS7下mysql5.7.37的卸载【完美方案】
- SQL注入 Less54(限制次数的SQL注入+union注入)
- The whole process scheduling, MySQL and Sqoop
- 19.支持向量机-优化目标和大间距直观理解
- 刚出道“一战成名”,安全、舒适一个不落
- Why is String immutable?
- mycat的主从关系 垂直分库 水平分表 以及mycat分片联表查询的配置详解(mysql5.7系列)
- [Android] Room - Alternative to SQLite
- The principle of complete replication of virtual machines (cloud computing)
猜你喜欢
数学解决——环形链表问题
CorelDRAW2022精简亚太新增功能详细介绍
Mathematics to solve the problem - circular linked list
YOLOV5学习笔记(三)——网络模块详解
19. Support Vector Machines - Intuitive Understanding of Optimization Objectives and Large Spacing
Why is String immutable?
JS function this context runtime syntax parentheses array IIFE timer delay self.backup context call apply
How to do a startup CTO?
Moxa NPort 设备缺陷可能使关键基础设施遭受破坏性攻击
12 Disk related commands
随机推荐
Software accumulation -- Screenshot software ScreenToGif
AI在医疗影像设备全流程应用
The application of AI in the whole process of medical imaging equipment
SQL injection Less46 (injection after order by + rand() Boolean blind injection)
CefSharp入门-winform
JS 函数 this上下文 运行时点语法 圆括号 数组 IIFE 定时器 延时器 self.备份上下文 call apply
SQL注入 Less54(限制次数的SQL注入+union注入)
【C语言】三子棋(经典解法+一览图)
TCP/IP four-layer model
YOLOV5学习笔记(二)——环境安装+运行+训练
医疗影像领域AI软件开发流程
加密公司向盗窃的黑客提供报价:保留一点,把剩下的归还
Unity3D Button 鼠标悬浮进入与鼠标悬浮退出按钮事件
华为分布式存储FusionStorage知识点总结【面试篇】
Clustering index, and what is the difference between a clustering index
Graphical lower_bound & upper_bound
CentOS7下mysql5.7.37的安装【完美方案】
Unity3D Button mouse hover enter and mouse hover exit button events
【C语言】表达式求值的一般方法
Moxa NPort 设备缺陷可能使关键基础设施遭受破坏性攻击