LeetCode contest 183 5376. 非递增顺序的最小子序列 Minimum Subsequence in Non-Increasing Order

简介: LeetCode contest 183 5376. 非递增顺序的最小子序列 Minimum Subsequence in Non-Increasing Order

LeetCode contest 183 5376. 非递增顺序的最小子序列 Minimum Subsequence in Non-Increasing Order


Table of Contents

一、中文版

二、英文版

三、My answer

四、解题报告


一、中文版

给你一个数组 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


二、英文版

Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.  
If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.  
Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.
Example 1:
Input: nums = [4,3,10,9,8]
Output: [10,9]  
Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included, however, the subsequence [10,9] has the maximum total sum of its elements.  
Example 2:
Input: nums = [4,4,7,6,7]
Output: [7,7,6]  
Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to returned in non-decreasing order.  
Example 3:
Input: nums = [6]
Output: [6]
Constraints:
1 <= nums.length <= 500
1 <= nums[i] <= 100


三、My answer

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums.sort(reverse=True)
        sum1, sum2 = 0, 0
        res = []
        for i in range(len(nums)):
            sum2 += nums[i]
        for i in range(len(nums)):
            sum1 += nums[i]
            res.append(nums[i])
            sum2 -= nums[i]
            if sum1 > sum2:
                return res


四、解题报告

根据题目要求 ——  

1、如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和最大 的子序列

2、返回的答案应当按 非递增顺序 排列

本人直接将 nums 数组逆序排列。

将数组 nums 分为两部分,前半部分的和严格大于后半部分。

sum1 表示前半部分的和,sum2 表示后半部分的和(初值为数组中所有数字之和),随着 i 后移,sum1 不断增大,sum2 不断减少,当出现第一个 sum1 > sum2 时,即为所求(贪心思想)。

相关文章
|
6天前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
6 1
|
7天前
|
存储 算法 数据可视化
哈希表法快速求解最长连续序列 | 力扣128题详细解析
哈希表法快速求解最长连续序列 | 力扣128题详细解析
|
7天前
|
存储 自然语言处理 算法
LeetCode题目115:不同子序列
LeetCode题目115:不同子序列
|
12天前
|
Java
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
|
12天前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
14 0
|
1月前
leetcode代码记录(最长连续递增序列
leetcode代码记录(最长连续递增序列
17 2
|
1月前
leetcode代码记录(最长递增子序列
leetcode代码记录(最长递增子序列
14 1
|
1月前
|
算法
leetcode代码记录(摆动序列
leetcode代码记录(摆动序列
17 0
|
1月前
|
算法
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
37 1
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题