2024-05-29:用 go 语言,给定一个只包含正整数的数组 nums,任务是通过多次操作最小化数组的长度。 每次操作可以从数组中选择两个不同的下标 i 和 j,使得 nums[i] 和 nums[j
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 完整代码如下:
![](https://static001.geekbang.org/infoq/0b/0bd90485a3a65394ffc1b4d808956f8c.png)
Python 完整代码如下:
![](https://static001.geekbang.org/infoq/74/74897166fa94672c0f5dbfe70e066d48.png)
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/0ae87975913783a0785c3c189】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论