当前位置:网站首页>LeetCode Question of the Day - 1403. Minimum Subsequence in Non-Increasing Order
LeetCode Question of the Day - 1403. Minimum Subsequence in Non-Increasing Order
2022-08-04 17:03:00 【SK_Jaco】
1.题目描述
给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和.
如果存在多个解决方案,只需返回 长度最小 的子序列.如果仍然有多个解决方案,则返回 元素之和最大 的子序列.
与子数组不同的地方在于,「数组的子序列」不强调元素在原数组中的连续性,也就是说,它可以通过从数组中分离一些(也可能不分离)元素得到.
注意,题目数据保证满足所有约束条件的解决方案是 唯一 的.同时,返回的答案应当按 非递增顺序 排列.
示例 1:
输入:nums = [4,3,10,9,8]
输出:[10,9]
解释:子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列.但是 [10,9] 的元素之和最大.
示例 2:
输入:nums = [4,4,7,6,7]
输出:[7,7,6]
解释:子序列 [7,7] 的和为 14 ,不严格大于剩下的其他元素之和(14 = 4 + 4 + 6).因此,[7,6,7] 是满足题意的最小子序列.注意,元素按非递增顺序返回.
示例 3:
输入:nums = [6]
输出:[6]
2.解题思路与代码
2.1 解题思路
这道题非常简单,The question asks to find the subsequence with the smallest length,And the sum of the subsequences is required to be greater than the sum of the elements outside the subsequence,Then we can think of if the sum of the subsequences is greater than half of the sum of the whole array,Then the sum of this subsequence must be greater than the sum of the rest of the elements.Start with this idea,我们先对数组进行排序,Then start traversing from the position with the largest number.The condition that the subsequence length required by the title is minimum and decreasing,Then we start summing from high,Exit until the sum is greater than half the sum of the array for the first time,This will give you the results.
以 [4,3,10,9,8] 为例,First we sort the array,And find the sum of the array as 34,Then we just need to find greater than 17 的子序列即可
The title requires subsequences in descending order and minimum length,Since the sorting is sorted from small to large,Then we traverse forward from the last bit of the array.when pointing to the last digit,The sum of the subsequences at this time is 10 小于 17.Because the title requires the result list to be sorted in descending order,因此将 10 放入结果列表中,然后继续向前移动
after moving forward,The sum of the subsequences is 19 大于 17 满足条件,将 9 Exit the loop after putting in the result list,At this point the subsequence in the resulting list is [10, 9]
2.2 代码
class Solution {
public List<Integer> minSubsequence(int[] nums) {
int sum = Arrays.stream(nums).sum() >> 1;
Arrays.sort(nums);
List<Integer> ans = new ArrayList<>();
int i = nums.length - 1;
int tmp = 0;
while (i >= 0) {
tmp += nums[i];
ans.add(nums[i]);
if (tmp > sum) {
break;
}
i--;
}
return ans;
}
}ji
2.3 测试结果
通过测试
3.总结
- 对数组进行排序,Then start traversing from the high position
- Find a sequence that is greater than the array value and half
边栏推荐
猜你喜欢
随机推荐
How to convert an int attribute into a string in the json format returned by the Go language gin framework?
生产环境重大bug,update加上索引字段会走索引进行更新?还是走全表扫描
小满nestjs(第一章 介绍nestjs)
taro 滚动组件ScrollView
湖北移动HG680-LV_S905L3B_线刷固件包
域名哪家便宜?怎么买便宜域名?
8月5日,麒麟信安邀您相约鲲鹏开发者创享日·长沙站!
mysql学习笔记——利用动态SQL和Session变量实现一个公式或者计算器
华硕win11安全启动如何开启
代码重构:面向单元测试
数字化金融企业的产品体系长啥样?
接口测试项目(非常值得练手)
SAP 电商云 Spartacus UI SSR 里 engine 和 engine instance 的区别
Mobile magic box CM201-1_CW_S905L2_MT7668_wire brush firmware package
电气成套设备行业如何借助ERP系统,解决企业管理难题?
Mobile Hisense IP102H_905L3-B_wire brush firmware package
88.(cesium之家)cesium聚合图
图扑软件与华为云共同构建新型智慧工厂
拼多多详情API接口深度解读
北京海淀6家必胜客被暂停外卖订餐 存在食品安全问题