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))

本作品采用《CC 协议》，转载必须注明作者和本文链接