旅游做攻略的网站有哪些,基层网站建设存在困难,深圳哪个区最好,做网站的公司怎么发展业务1. 题目
给你一个数组 nums#xff0c;请你从中抽取一个子序列#xff0c;满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案#xff0c;只需返回 长度最小 的子序列。如果仍然有多个解决方案#xff0c;则返回 元素之和最大 的子…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]提示
1 nums.length 500
1 nums[i] 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 sort排序
降序排列找到前缀和大于剩余和的第一个位置
class Solution {
public:vectorint minSubsequence(vectorint nums) {sort(nums.rbegin(), nums.rend());int i, sum 0, s 0;for(i 0; i nums.size(); i)sum nums[i];for(i 0; i nums.size(); i){if(nums[i] s sum - nums[i])break;else{s nums[i];sum - nums[i];}}return vectorint(nums.begin(),nums.begin()i1);}
};20 ms 10.9 MB
2.2 计数排序
class Solution {
public:vectorint minSubsequence(vectorint nums) {int count[101] {0};int i, sum 0, s 0;for(i 0; i nums.size(); i){sum nums[i];count[nums[i]];}vectorint ans;for(i 100; i 0; --i){while(count[i]--){if(si sum-i){ans.push_back(i);return ans;}else{s i;sum - i;ans.push_back(i);}}}return ans;}
};28 ms 10.8 MB
