当前位置:网站首页>leetcode-每日一题1403. 非递增顺序的最小子序列(贪心)
leetcode-每日一题1403. 非递增顺序的最小子序列(贪心)
2022-08-05 03:19:00 【lin钟一】
题目链接:https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/
思路
方法一、贪心
题目的大致意思就是把数组分成两个序列,一个序列元素之和严格大于另一个序列元素之和,且满足前面的序列元素最大、长度最短两个要求,所以很简单,我们只需要把数组从大到小排序一遍,计算整个数组之和,然后贪心去取数组的最大值,直到序列元素之和严格大于另一个序列元素之和
代码示例
func minSubsequence(nums []int) []int {
sort.Slice(nums, func(i, j int) bool {
return nums[i] > nums[j]})
tot := 0
for _, num := range nums {
tot += num
}
for i, sum := 0, 0; ; i++ {
sum += nums[i]
if sum > tot-sum {
return nums[:i+1]
}
}
}
复杂度分析
- 时间复杂度:O(n logn) 其中n时数组长度,对数组进行排序需要O(n logn)的时间,对数组进行遍历需要O(n)的时间
- 空间复杂度:O(1) 不需要额外再申请空间
边栏推荐
- Study Notes-----Left-biased Tree
- The second council meeting of the Dragon Lizard Community was successfully held!Director general election, 4 special consultants joined
- Summary of domestic environments supported by SuperMap
- Common open source databases under Linux, how many do you know?
- 1667. Fix names in tables
- 开发Hololens遇到The type or namespace name ‘HandMeshVertex‘ could not be found..
- ASP.NET应用程序--Hello World
- Open Source License Description LGPL
- 北斗三号短报文终端露天矿山高边坡监测方案
- Review 51 MCU
猜你喜欢
2022高处安装、维护、拆除考试题模拟考试题库及在线模拟考试
Beyond YOLO5-Face | YOLO-FaceV2 officially open source Trick+ academic point full
使用二维码传输文件的小工具 - QFileTrans 1.2.0.1
腾讯云【Hiflow】新时代自动化工具
.NET应用程序--Helloworld(C#)
presto启动成功后出现2022-08-04T17:50:58.296+0800 ERROR Announcer-3 io.airlift.discovery.client.Announcer
[Filter tracking] based on matlab unscented Kalman filter inertial navigation + DVL combined navigation [including Matlab source code 2019]
毕设-基于SSM房屋租赁管理系统
ASP.NET application--Hello World
J9 Digital Currency: What is the creator economy of web3?
随机推荐
软链接引发的物理备份问题
Use SuperMap iDesktopX data migration tool to migrate ArcGIS data
private package
Ant Sword Advanced Module Development
用CH341A烧录外挂Flash (W25Q16JV)
Flink 1.15.1 Cluster Construction (StandaloneSession)
A small tool to transfer files using QR code - QFileTrans 1.2.0.1
【七夕节】浪漫七夕,代码传情。将爱意变成绚烂的立体场景,给她(他)一个惊喜!(送代码)
21 Days Learning Challenge (2) Use of Graphical Device Trees
Syntax basics (variables, input and output, expressions and sequential statements)
undo problem
如何在WordPress中添加特定类别的小工具
shell脚本:for循环与while循环
链表的简单描述及代码的简单实现
burp安装及代理设置
YYGH-13-客服中心
【软件测试】自动化测试之unittest框架
语法基础(变量、输入输出、表达式与顺序语句完成情况)
QStyle platform style
Physical backup issues caused by soft links