Easy

题目描述

给你一个正整数数组 nums 和一个整数 k。

从 nums 中选择最多 k 个元素，使得它们的和最大化。但是，所选择的数字必须是不同的。

返回一个包含所选数字的数组，按严格递减顺序排列。

示例 1：

输入：nums = [84,93,100,77,90], k = 3
输出：[100,93,90]
解释：
最大和是 283，通过选择 93、100 和 90 得到。我们将它们按严格递减顺序重新排列为 [100, 93, 90]。

示例 2：

输入：nums = [84,93,100,77,93], k = 3
输出：[100,93,84]
解释：
最大和是 277，通过选择 84、93 和 100 得到。我们将它们按严格递减顺序重新排列为 [100, 93, 84]。我们不能选择 93、100 和 93，因为所选择的数字必须是不同的。

示例 3：

输入：nums = [1,1,1,2,2,2], k = 6
输出：[2,1]
解释：
最大和是 3，通过选择 1 和 2 得到。我们将它们按严格递减顺序重新排列为 [2, 1]。

约束条件：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

解题思路

解题思路

这道题的核心思想是贪心算法：要使和最大化，我们应该选择最大的不重复元素。

算法步骤：

  1. 去重处理：由于要求选择的元素必须是不同的，首先需要对数组进行去重操作。可以使用集合(Set)来实现。

  2. 降序排序：将去重后的元素按降序排列，这样最大的元素会排在前面。

  3. 选择前k个元素：从排序后的数组中选择前min(k, 去重后数组长度)个元素，因为如果去重后的元素个数少于k，我们只能选择所有去重后的元素。

  4. 返回结果：由于我们已经按降序排序，直接返回选择的元素即可。

时间复杂度分析：

  • 去重操作：O(n)
  • 排序操作：O(m log m)，其中m是去重后的元素个数
  • 选择操作：O(k)
  • 总体：O(n + m log m)

这种方法简单直观，利用了贪心策略的最优性：为了获得最大和，我们总是优先选择最大的可用元素。

代码实现

class Solution {
public:
    vector<int> maxKDistinct(vector<int>& nums, int k) {
        set<int> uniqueNums(nums.begin(), nums.end());
        vector<int> sortedNums(uniqueNums.rbegin(), uniqueNums.rend());
        
        int selectCount = min(k, (int)sortedNums.size());
        return vector<int>(sortedNums.begin(), sortedNums.begin() + selectCount);
    }
};

class Solution:
    def maxKDistinct(self, nums: List[int], k: int) -> List[int]:
        unique_nums = list(set(nums))
        unique_nums.sort(reverse=True)
        
        select_count = min(k, len(unique_nums))
        return unique_nums[:select_count]

public class Solution {
    public int[] MaxKDistinct(int[] nums, int k) {
        var uniqueNums = new HashSet<int>(nums).ToArray();
        Array.Sort(uniqueNums, (a, b) => b.CompareTo(a));
        
        int selectCount = Math.Min(k, uniqueNums.Length);
        int[] result = new int[selectCount];
        Array.Copy(uniqueNums, result, selectCount);
        return result;
    }
}

var maxKDistinct = function(nums, k) {
    const uniqueNums = [...new Set(nums)];
    uniqueNums.sort((a, b) => b - a);
    
    const selectCount = Math.min(k, uniqueNums.length);
    return uniqueNums.slice(0, selectCount);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
去重O(n)O(m)
排序O(m log m)O(1)
选择O(k)O(k)
总计O(n + m log m)O(m)

其中 n 是原数组长度，m 是去重后的元素个数，k 是要选择的元素个数。