X

LEETCODE 1403. Minimum Subsequence in Non-Increasing Order 解题思路分析

题目大意:

非递增顺序的最小子序列

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1403

解题思路分析:

虽然这是一道Easy题目,但还是需要我们稍微动一下脑筋。首先考虑2点:

  1. 我们将数组分成任意两部分,如果要保证其中一个部分的数字和大于另一部分,那么该部分数字和一定大于数组中所有数字之和的一半。
  2. 题目要求长度最小的符合条件的子序列,长度小也就代表子序列中的元素个数少,既然个数要求尽量少,那么每个元素的数值就要保证尽量大才行。

解题时,我们先对数组进行排序。然后假设数组长度是n,我们将数组分成长度为0和n两个部分,此时长度为n的这个部分的元素和一定大于长度为0的部分(废话)。然后我们开始循环尝试从长度为n的部分中减去一个最小值,之后查看剩下的元素和是否大于数组总和的一半,如果大于,则重复上述过程。反之退出循环。剩下的元素即是我们要求的结果。

当然这道题反过来做也可行,我们向长度为0的部分加入一个最大值,如果当前数值和小于等于数组所有元素和的一半,继续从剩下的元素中找一个最大值添加进当前子序列。当子序列中元素数字和大于所有元素和的一半时,当前子序列即是返回结果。

总结一下,本题实际上是在利用贪心算法解题。如果暴力解我们需要遍历所有分组情况,然后再找到一个最优解。贪心算法的核心是,我们利用数组中前n大的数字组成的子序列一定是满足条件下序列长度最小的结果。

实现代码:

public List<Integer> minSubsequence(int[] nums) {
    Arrays.sort(nums); // 排序数组
    int sum=0; // 数组中元素和
    for(int n : nums) sum+=n;
    int half = sum/2+1; // 元素和的一半
    // 返回结果
    List<Integer> res = new ArrayList<>();
    // 序列元素和
    int sequenceSum=0;
    for(int i=nums.length-1;i>=0;i--){
        // 将当前最大元素加入到返回结果
        res.add(nums[i]);
        // 累加子序列元素和
        sequenceSum+=nums[i];
        // 如果子序列元素和大于数组所有元素和的一半,退出循环
        if(sequenceSum>=half) break;
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 98.60% of Java online submissions for Minimum Subsequence in Non-Increasing Order.

Memory Usage: 39.1 MB, less than 100.00% of Java online submissions for Minimum Subsequence in Non-Increasing Order.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1403-minimum-subsequence-in-non-increasing-order-解题思路分析/
Categories: leetcode
kwantong: