2024-05-29：用 go 语言，给定一个只包含正整数的数组 nums，任务是通过多次操作最小化数组的长度。

每次操作可以从数组中选择两个不同的下标 i 和 j，使得 nums[i] 和 nums[j] 均为正整数。

然后，将 nums[i] 除以 nums[j] 的余数插入数组末尾，同时删除原始的两个元素。

最终要求计算进行操作后的最短数组长度。

输入：nums = [1,4,3,1]。

输出：1。

答案 2024-05-29：

chatgpt

题目来自 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))