当前位置:网站首页>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)]
边栏推荐
- STM32CUBEMX develops GD32F303 (11) ---- ADC scans multiple channels in DMA mode
- 15、网站统计数据
- 【Bank Series Phase 1】People's Bank of China
- The whole process scheduling, MySQL and Sqoop
- 11、Redis实现关注、取消关注以及关注和粉丝列表
- Huawei od dice js
- 【银行系列第一期】中国人民银行
- mycat的主从关系 垂直分库 水平分表 以及mycat分片联表查询的配置详解(mysql5.7系列)
- Discussion on Service Commitment of Class Objects under Multithreading
- 基于opencv实现人脸检测
猜你喜欢
IIR滤波器和FIR滤波器
基于opencv实现人脸检测
f.grid_sample
CorelDRAW2022 streamlined Asia Pacific new features in detail
Hanyuan Hi-Tech 8-channel HDMI integrated multi-service high-definition video optical transceiver 8-channel HDMI video + 8-channel two-way audio + 8-channel 485 data + 8-channel E1 + 32-channel teleph
Pythagorean tuple od js
JS function this context runtime syntax parentheses array IIFE timer delay self.backup context call apply
What is distributed and clustered?What is the difference?
LeetCode 1161 The largest element in the layer and the LeetCode road of [BFS binary tree] HERODING
6. Display comments and replies
随机推荐
拒绝加班,程序员开发的效率工具集
Intel's software and hardware optimization empowers Neusoft to accelerate the arrival of the era of smart medical care
6. Display comments and replies
Face detection based on opencv
Multilingual settings of php website (IP address distinguishes domestic and foreign)
6、显示评论和回复
How to build a private yum source
刚出道“一战成名”,安全、舒适一个不落
关于 mysql8.0数据库中主键位id,使用replace插入id为0时,实际id插入后自增导致数据重复插入 的解决方法
Mathematical Ideas in AI
print task sorting js od huawei
YOLOV5学习笔记(二)——环境安装+运行+训练
工程(五)——小目标检测tph-yolov5
CMOS和TTL的区别?
Intranet Infiltration - Privilege Escalation
The modification is not properly placed in the sandbox, causing Apple compatibility issues
Linux下redis7的安装,启动与停止
Go 项目实战-获取多级分类下的全部商品
12 Disk related commands
Word/Excel fixed table size, when filling in the content, the table does not change with the cell content