2026-02-13：至多 K 个不同元素的最大和。用go语言，输入为一个仅包含正整数的列表 nums 和一个整数 k。要求从该列表中挑出不多于 k 个互不相同的数，使这组数的和尽可能大。结果以一个数组返回，数组中的元素按从大到小的顺序排列（严格递减）。
1 <= nums.length <= 100。
1 <= nums[i] <= 1000000000。
1 <= k <= nums.length。
输入： nums = [84,93,100,77,90], k = 3。
输出： [100,93,90]。
解释：
最大和为 283，可以通过选择 93、100 和 90 实现。将它们按严格递减顺序排列，得到 [100, 93, 90]。
题目来自力扣3684。
🛠️ 分步骤过程描述
降序排序
首先，代码使用 slices.SortFunc 对输入的整数切片 nums 进行降序（从大到小）排序。排序函数 func(a, b int) int { return b – a } 通过计算 b – a 来确定顺序，如果结果为负数，说明 a 应排在 b 后面，从而实现了降序排列。这一步的目的是将最大的数字放在最前面，为后续选择做准备。排序后的结果为 [100, 93, 90, 84, 77]。
原地去重
接着，代码使用 slices.Compact 函数对已排序的切片进行去重操作。slices.Compact 会修改原始切片，通过将连续不重复的元素依次前移，并返回一个只包含不重复元素的新切片。由于上一步已经进行了排序，所有相同的数字都会紧挨在一起，因此 slices.Compact 可以高效地移除所有重复项，只保留每个值的第一次出现。例如，如果原数组有重复的 100，这一步后也只会保留一个。
选择前K个元素
去重后，代码通过切片操作 nums[:min(k, len(nums))] 来选取最终结果。这个操作会取当前 nums 切片的前 min(k, len(nums)) 个元素。这里的 min 函数（代码中未显式定义，但逻辑上是取最小值）是一个保护性措施，确保当所需的不同元素数量 k 大于切片中实际存在的不同元素数量时，不会发生数组越界错误。最终，函数返回这个包含至多 k 个最大不同元素的切片。
⏱️ 复杂度分析
-
总的时间复杂度：该算法的时间复杂度主要由排序步骤决定。slices.SortFunc 使用的排序算法（如快速排序）的平均时间复杂度为 O(n log n)，其中 n 是输入列表 nums 的长度。去重操作 slices.Compact 需要遍历整个切片，时间复杂度为 O(n)。选择前K个元素是 O(1) 的切片操作。因此，总的时间复杂度为 O(n log n) + O(n)，主导项是 O(n log n)。
-
总的额外空间复杂度：该算法的空间效率很高。排序操作 slices.SortFunc 是原地进行的，通常需要 O(log n) 的栈空间（递归深度）。去重操作 slices.Compact 也是原地完成的，不需要额外分配空间。因此，总的额外空间复杂度为 O(log n)。
Go完整代码如下：
package main
import (
"fmt"
"slices"
)
func maxKDistinct(nums []int, k int) []int {
slices.SortFunc(nums, func(a, b int) int { return b – a })
nums = slices.Compact(nums) // 原地去重
return nums[:min(k, len(nums))]
}
func main() {
nums := []int{84, 93, 100, 77, 90}
k := 3
result := maxKDistinct(nums, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def max_k_distinct(nums, k):
# 降序排序
nums = sorted(nums, reverse=True)
# 去重并保持顺序
seen = set()
unique_nums = []
for num in nums:
if num not in seen:
seen.add(num)
unique_nums.append(num)
# 返回前k个元素
return unique_nums[:min(k, len(unique_nums))]
def main():
nums = [84, 93, 100, 77, 90]
k = 3
result = max_k_distinct(nums, k)
print(result)
if __name__ == "__main__":
main()
C++完整代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
std::vector<int> maxKDistinct(std::vector<int> nums, int k) {
// 降序排序
std::sort(nums.begin(), nums.end(), std::greater<int>());
// 去重
std::unordered_set<int> seen;
std::vector<int> unique_nums;
for (int num : nums) {
if (seen.find(num) == seen.end()) {
seen.insert(num);
unique_nums.push_back(num);
}
}
// 返回前k个元素
int limit = std::min(k, (int)unique_nums.size());
return std::vector<int>(unique_nums.begin(), unique_nums.begin() + limit);
}
int main() {
std::vector<int> nums = {84, 93, 100, 77, 90};
int k = 3;
std::vector<int> result = maxKDistinct(nums, k);
for (int i = 0; i < result.size(); ++i) {
std::cout << result[i];
if (i < result.size() – 1) {
std::cout << " ";
}
}
std::cout << std::endl;
return 0;
}
