2026-02-13：至多 K 个不同元素的最大和。用go语言，输入为一个仅包含正整数的列表 nums 和一个整数 k。要求从该列表中挑出不多于 k 个互不相同的数，使这组数的和尽可能大。结果以一个数组返回，数组中的元素按从大到小的顺序排列（严格递减）。
1
1
1
输入： nums = [84,93,100,77,90], k = 3。
输出： [100,93,90]。
解释：
最大和为 283，可以通过选择 93、100 和 90 实现。将它们按严格递减顺序排列，得到 [100, 93, 90]。
题目来自力扣3684。
️ 分步骤过程描述
1. 降序排序
首先，代码使用 slices.SortFunc 对输入的整数切片 nums 进行降序（从大到小）排序。排序函数 func(a, b int) int { return b - a } 通过计算 b - a 来确定顺序，如果结果为负数，说明 a 应排在 b 后面，从而实现了降序排列。这一步的目的是将最大的数字放在最前面，为后续选择做准备。排序后的结果为 [100, 93, 90, 84, 77]。
2. 原地去重
接着，代码使用 slices.Compact 函数对已排序的切片进行去重操作。slices.Compact 会修改原始切片，通过将连续不重复的元素依次前移，并返回一个只包含不重复元素的新切片。由于上一步已经进行了排序，所有相同的数字都会紧挨在一起，因此 slices.Compact 可以高效地移除所有重复项，只保留每个值的第一次出现。例如，如果原数组有重复的 100，这一步后也只会保留一个。
3. 选择前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
#include
#include
#include
std::vector maxKDistinct(std::vector nums, int k) {
// 降序排序
std::sort(nums.begin, nums.end, std::greater);
// 去重
std::unordered_set seen;
std::vector 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(unique_nums.begin, unique_nums.begin + limit);
}
int main {
std::vector nums = {84, 93, 100, 77, 90};
int k = 3;
std::vector result = maxKDistinct(nums, k);
for (int i = 0; i
std::cout
if (i
std::cout
}
}
std::cout
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
配资安全配资门户提示：文章来自网络，不代表本站观点。
