数组元素之和最小化
- 问题描述
- 思路分析
- 分析
- 思路
- 解决方案
- 参考代码(Python)
- 代码分析
- 1. `solution` 函数
- 2. 计算 `1 + 2 + 3 + ... + n` 的和
- 3. 乘以 `k` 得到最终的数组元素之和
- 4. 主程序(`if __name__ == '__main__':`)
- 代码的时间复杂度分析:
- 代码的空间复杂度分析:
问题描述
思路分析
分析
- 元素两两不同:数组中所有元素必须是不同的。
- 元素的最大公约数为 k:所有的元素必须是
k
的倍数。 - 元素之和尽可能小:为了让元素的和最小,我们需要尽量选择最小的满足条件的元素。
思路
- 首先,如果数组元素的最大公约数为
k
,那么所有元素可以表示成k * a1, k * a2, ..., k * an
的形式,其中a1, a2, ..., an
是n
个互质的数。 - 为了满足“元素之和尽可能小”,我们应该选择最小的
n
个互质数,且这些数的公约数为 1。 - 最小的
n
个互质数依次是:1, 2, 3, …, n。
解决方案
- 选择最小的
n
个互质数,分别是1, 2, 3, ..., n
。 - 这些数分别乘以
k
,得到的数组为k, 2k, 3k, ..., nk
。 - 最终的数组元素之和就是
k * (1 + 2 + 3 + ... + n)
。
1 + 2 + 3 + ... + n
的和是一个已知公式:n * (n + 1) / 2
。
因此,数组的最小和就是 k * (n * (n + 1) / 2)
。
参考代码(Python)
def solution(n: int, k: int) -> int:# 计算 1 + 2 + 3 + ... + n 的和sum_of_first_n = n * (n + 1) // 2# 乘以 k 得到最终的和return k * sum_of_first_nif __name__ == '__main__':print(solution(n = 3, k = 1) == 6) # 1+2+3 = 6print(solution(n = 2, k = 2) == 6) # 2+4 = 6print(solution(n = 4, k = 3) == 30) # 3+6+9+12 = 30
代码分析
1. solution
函数
def solution(n: int, k: int) -> int:
- 功能:该函数的作用是返回一个包含
n
个元素的数组,其满足题目的条件:数组中的元素两两不同,所有元素的最大公约数为k
,并且这些元素之和尽可能小。 - 参数:
n
: 数组中元素的个数。k
: 数组中每个元素的最大公约数。
2. 计算 1 + 2 + 3 + ... + n
的和
sum_of_first_n = n * (n + 1) // 2
-
解释:为了尽可能使数组元素之和最小,我们选择最小的
n
个互质数,这些数是1, 2, 3, ..., n
。 -
数学公式:
1 + 2 + 3 + ... + n
的和是一个经典的数学公式:
该公式计算的是从 1 到
n
的所有整数的和。这个公式的时间复杂度是 O(1),只需要常数时间即可计算出结果。 -
具体实现:使用整数除法
//
来确保计算结果为整数(在 Python 中,/
默认会返回浮动类型,而我们这里需要整数结果)。
3. 乘以 k
得到最终的数组元素之和
return k * sum_of_first_n
- 解释:计算完
1 + 2 + 3 + ... + n
的和后,乘以k
得到数组中所有元素的和。- 例如,数组中的元素是
k, 2k, 3k, ..., nk
,这些元素的和就是k * (1 + 2 + 3 + ... + n)
,即k
乘以sum_of_first_n
。 - 由于我们已经在前一步计算了
sum_of_first_n
,这一步是将它乘以k
得到最终的结果。
- 例如,数组中的元素是
4. 主程序(if __name__ == '__main__':
)
if __name__ == '__main__':print(solution(n = 3, k = 1) == 6) # 1+2+3 = 6print(solution(n = 2, k = 2) == 6) # 2+4 = 6print(solution(n = 4, k = 3) == 30) # 3+6+9+12 = 30
- 这里的
if __name__ == '__main__':
用来检查该文件是否作为主程序执行。如果是,代码就会运行里面的测试代码;如果这个文件被作为模块导入,里面的测试代码就不会执行。 - 测试:
solution(n = 3, k = 1)
返回的是6
,因为选取的是1, 2, 3
,它们的和是6
。solution(n = 2, k = 2)
返回的是6
,选取的是2, 4
,它们的和是6
。solution(n = 4, k = 3)
返回的是30
,选取的是3, 6, 9, 12
,它们的和是30
。
代码的时间复杂度分析:
- 计算和
1 + 2 + 3 + ... + n
:这部分使用了数学公式,时间复杂度是 O(1)。 - 乘以
k
:这只是一个常数乘法操作,时间复杂度也是 O(1)。 - 总时间复杂度:由于这两个操作的时间复杂度都是 O(1),所以整体时间复杂度是 O(1)。
代码的空间复杂度分析:
- 该函数只使用了常数空间(除了输入和输出),所以空间复杂度也是 O(1)。