2024-05-29：用go语言，给定一个只包含正整数的数组 nums，任务是通过多次操作最小化数组的长度。
每次操作可以从数组中选择两个不同的下标 i 和 j，使得 nums[i] 和 nums[j] 均为正整数。
然后，将 nums[i] 除以 nums[j] 的余数插入数组末尾，同时删除原始的两个元素。
最终要求计算进行操作后的最短数组长度。
输入：nums = [1,4,3,1]。
输出：1。
答案2024-05-29：
题目来自leetcode3012。
大体步骤如下：
1.定义一个函数 minimumArrayLength(nums []int) int，该函数接收一个整数数组 nums 作为输入并返回一个整数作为输出。
2.使用 slices.Min(nums) 函数找到数组 nums 中的最小值，将其赋值给变量 m。
3.对数组 nums 中的每个元素执行以下操作：
- 如果当前元素除以
m的余数大于 0，则直接返回 1。这意味着无法通过操作将该元素减小到0。
4.初始化一个计数器 cnt 为0，然后对数组 nums 中的每个元素执行以下操作：
- 如果当前元素等于
m，则增加计数器cnt的值。
5.最终返回操作完成后的数组最小长度：(cnt + 1) / 2。这表示将 m 减小到0所需的最小步骤数。
总的时间复杂度：
-
找到最小值
m的时间复杂度为 O(n)，其中 n 是输入数组的长度。 -
遍历输入数组
nums两次以查找余数不为0的元素和统计m的数量的时间复杂度为 O(n)。
综合来看，总的时间复杂度为 O(n)。
总的额外空间复杂度：
- 除了输入数组外，算法使用了几个整数变量来进行计算，这些变量的额外空间消耗是常量级的。
所以，总的额外空间复杂度为 O(1)。
Go完整代码如下：
package main
import (
"fmt"
"slices"
)
func minimumArrayLength(nums []int) int {
m := slices.Min(nums)
for _, x := range nums {
if x%m > 0 {
return 1
}
}
cnt := 0
for _, x := range nums {
if x == m {
cnt++
}
}
return (cnt + 1) / 2
}
func main() {
nums := []int{1,4,3,1}
fmt.Println(minimumArrayLength(nums))
}
Python完整代码如下：
# -*-coding:utf-8-*-
import math
def minimum_array_length(nums):
m = min(nums)
for x in nums:
if x % m > 0:
return 1
cnt = 0
for x in nums:
if x == m:
cnt += 1
return (cnt + 1) // 2
nums = [1, 4, 3, 1]
print(minimum_array_length(nums))
