当前位置:网站首页>LeetCode simple problem to find the subsequence of length K with the largest sum
LeetCode simple problem to find the subsequence of length K with the largest sum
2022-07-31 03:04:00 【·The sea of stars】
题目
给你一个整数数组 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)
解题思路
The result array required by this question does not need to be contiguous in the original array,This greatly reduces the difficulty of the problem,So the first step is to sort the given array first,Then take the largest elements and their subscripts,Then intercept the results that meet the conditions and return the correct sequence in the original array.
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]
Of course, this question does not need to be completely sorted,The best way to do this is to use selection sort to match the conditionskAfter one is selected, it will not continue to sort.
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)]
边栏推荐
- SQL注入 Less46(order by后的注入+rand()布尔盲注)
- 2022 Nioke Multi-School League Game 4 Solution
- 4. Sensitive word filtering (prefix tree)
- Map.Entry理解和应用
- Getting Started with CefSharp - winform
- [Android] Room - Alternative to SQLite
- 接口测试关键技术
- TCP/IP four-layer model
- YOLOV5 study notes (2) - environment installation + operation + training
- SQALE 是什么
猜你喜欢
JS 函数 this上下文 运行时点语法 圆括号 数组 IIFE 定时器 延时器 self.备份上下文 call apply
Mysql 45讲学习笔记(二十三)MYSQL怎么保证数据不丢
Chapter 9 SVM Practice
品牌广告投放平台的中台化应用与实践
Graphical lower_bound & upper_bound
Office automation case: how to automatically generate period data?
CorelDRAW2022 streamlined Asia Pacific new features in detail
10 权限介绍
LeetCode中等题之分数加减运算
Mysql 45讲学习笔记(二十四)MYSQL主从一致
随机推荐
LeetCode简单题之找到和最大的长度为 K 的子序列
4、敏感词过滤(前缀树)
分布式与集群是什么 ? 区别是什么?
Modbus on AT32 MCUs
Chapter 9 SVM实践
分布式系统架构需要解决的问题
SQL注入 Less54(限制次数的SQL注入+union注入)
10、Redis实现点赞(Set)和获取总点赞数
Mycat's master-slave relationship, vertical sub-database, horizontal sub-table, and detailed configuration of mycat fragmented table query (mysql5.7 series)
11、Redis实现关注、取消关注以及关注和粉丝列表
字体压缩神器font-spider的使用
SQL injection Less47 (error injection) and Less49 (time blind injection)
SQL 面试用题(重点)
Mysql 45讲学习笔记(二十四)MYSQL主从一致
Number 16, top posts
你们程序员为什么不靠自己的项目谋生?而必须为其他人打工?
VS QT——ui不显示新添加成员(控件)||代码无提示
工程(五)——小目标检测tph-yolov5
MP使用时的几个常见报错
SQL injection Less46 (injection after order by + rand() Boolean blind injection)