Easy

题目描述

给你一个数组 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] 满足该条件。注意，返回的子序列必须按非递增顺序排列。

提示：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 100

解题思路

这是一个贪心算法问题。我们需要找到一个最小长度的子序列，使其元素和严格大于剩余元素和。

解题思路：

  1. 贪心策略：要使子序列长度最小且元素和最大，我们应该优先选择最大的元素。因此首先对数组进行降序排序。

  2. 选择元素：从最大的元素开始，依次加入子序列，直到子序列的和严格大于剩余元素的和为止。

  3. 判断条件：设子序列当前和为 subSum，总和为 totalSum，当 subSum > totalSum - subSum 即 subSum > totalSum / 2 时，条件满足。

  4. 返回结果：由于我们按降序遍历，得到的子序列天然满足非递增顺序的要求。

算法步骤：

  • 计算数组总和
  • 将数组按降序排序
  • 从最大元素开始累加，直到累加和大于总和的一半
  • 返回选中的元素组成的子序列

这种贪心策略保证了子序列长度最小，同时在长度相同的情况下元素和最大。

代码实现

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        sort(nums.begin(), nums.end(), greater<int>());
        
        vector<int> result;
        int subSum = 0;
        
        for (int num : nums) {
            subSum += num;
            result.push_back(num);
            if (subSum > totalSum - subSum) {
                break;
            }
        }
        
        return result;
    }
};

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        total_sum = sum(nums)
        nums.sort(reverse=True)
        
        result = []
        sub_sum = 0
        
        for num in nums:
            sub_sum += num
            result.append(num)
            if sub_sum > total_sum - sub_sum:
                break
        
        return result

public class Solution {
    public IList<int> MinSubsequence(int[] nums) {
        int totalSum = nums.Sum();
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        
        IList<int> result = new List<int>();
        int subSum = 0;
        
        foreach (int num in nums) {
            subSum += num;
            result.Add(num);
            if (subSum > totalSum - subSum) {
                break;
            }
        }
        
        return result;
    }
}

var minSubsequence = function(nums) {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    nums.sort((a, b) => b - a);
    
    const result = [];
    let subSum = 0;
    
    for (const num of nums) {
        subSum += num;
        result.push(num);
        if (subSum > totalSum - subSum) {
            break;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要时间消耗在排序操作上，其中 n 为数组长度
空间复杂度O(1)除了返回结果数组外，只使用了常数级别的额外空间

相关题目