逐日一题-力扣-2829. k-avoiding 数组的最小总和 0326

办理"k-avoiding 数组的最小总和"题目

这道题有两种重要解法。
解法一：直接数学盘算（最优解）

通过数学推导直接盘算出效果，不必要构建实际的数组。

1. class Solution:
2.     def minimumSum(self, n: int, k: int) -> int:
3.         # 特殊情况：当k很大或k=1时，可以直接选择前n个正整数
4.         if k > 2*n or k <= 1:
5.             return n * (n + 1) // 2
6.         
7.         half_k = k // 2
8.         chosen_count = min(n, half_k)
9.         
10.         # 计算前half_k个数的和
11.         first_sum = chosen_count * (chosen_count + 1) // 2
12.         
13.         # 如果已经选择了n个数，直接返回结果
14.         if chosen_count == n:
15.             return first_sum
16.         
17.         # 否则，计算从k开始的剩余数字的和
18.         remaining_count = n - chosen_count
19.         start = k
20.         end = k + remaining_count - 1
21.         remaining_sum = (start + end) * remaining_count // 2
22.         
23.         return first_sum + remaining_sum

复制代码

思绪剖析：

• 必要找到n个差别的正整数，使得没有两个数的和即是k，且总和最小。
  
• 为了最小化总和，总是实验包罗尽大概小的正整数。
  
• 对于任何一个数x，不能同时包罗x和k-x（否则它们的和就是k）。
  
• 当x < k/2时，x < k-x，以是为了最小化总和，应该选择x而不是k-x。
  
• 因此，可以安全地包罗1到k/2的全部数。
  
• 对于k/2 < x < k的数，它们的互补数k-x已经在选择的聚集中（由于k-x < k/2），以是必须跳过这些数。
  
• 对于x ≥ k的数，它们的互补数k-x ≤ 0，不在正整数聚集中，以是可以安全包罗。
  

时间复杂度：O(1)，只必要举行简单的数学盘算。
空间复杂度：O(1)，只利用常数空间。
解法二：贪心方法 + 聚集

通过维护一个聚集，贪心地选择最小的可行数字：

1. class Solution:
2.     def minimumSum(self, n: int, k: int) -> int:
3.         s = set()
4.         num = 1
5.         
6.         while len(s) < n:
7.             if k - num not in s:
8.                 s.add(num)
9.             num += 1
10.         
11.         return sum(s)

复制代码

思绪剖析：

• 维护一个已选择数字的聚集s。
  
• 从1开始，实验将每个数字到场序列。
  
• 对于每个数字num，查抄其互补数(k-num)是否已在聚集中。假如不在，则可以到场num。
  
• 继续此过程直到聚集中有n个数字。
  

时间复杂度：O(n)，最多必要查抄2n个数字。
空间复杂度：O(n)，必要存储n个数字。
示例分析

以示例1为例，n=5, k=4：

• 解法一中，half_k = 2，起首选择1和2。
  
• 然后跳过3（由于4-3=1，而1已经在聚集中）。
  
• 然后从4开始选择剩余的数字：4,5,6。
  
• 终极序列是[1,2,4,5,6]，总和为18。
  

两种解法都能得到准确效果，但第一种解法更高效，时间复杂度为常数级。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告