附加 K 个整数以最小化总和的问题

问题陈述

给定一个整数数组 nums 和一个整数 k。在 nums 中附加 k 个不存在的唯一正整数，使得结果的总和最小。

返回附加到 nums 的 k 个整数的总和。

Java 方法（使用 HashSet）

输出

代码解释

• 该代码旨在找到一个已排序数组中前 k 个唯一元素的最小总和。它使用一个集合来跟踪遇到的元素并确保唯一性。数组已排序，并且对于每个元素，如果它既是唯一的又小于或等于 k，则 k 的值会增加，并且该元素会被添加到总和中。
• 最终结果通过从前 k 个自然数的总和中减去实际总和来计算。

时间复杂度

• 时间复杂度由算法的排序部分决定，该部分运行时间为 O(n log n)，其中 n 代表长度。对排序数组和集合操作的第二次迭代引入了线性时间，使聚合复杂度保持在 O(n log n)。

空间复杂度

• 由于我们使用内存结构 HashSet 来存储唯一元素，因此空间复杂度为 O(n)。当所有元素都不同时，HashSet 的大小将与输入数组的长度成正比，因此导致线性空间复杂度。

Java 最佳方法

输出

代码解释

• 该代码旨在找到给定数组“nums”中不存在的前“k”个唯一正整数的最小总和。它首先对数组进行排序，然后遍历排序后的元素。对于每个元素，它会检查它是否大于当前的“lo”值。如果为真，则计算“lo”和“num-1”之间缺失的正整数的范围。
• 它将此范围的总和添加到答案中，并更新“lo”和“k”。该过程一直持续到“k”变为零或所有元素都被处理完毕。

时间复杂度

• 该算法的时间复杂度为 O (N log N)，其中 N 是数组“nums”中的元素数量。排序是占用 O(N log N) 时间的最大因素。

空间复杂度

• 空间复杂度为 O(1)。对于“and”、“lo”、“hi”、“cnt”和“k”等变量，该算法需要恒定的额外空间，这与输入大小无关。