题目描述
给你一个下标从 0 开始的整数数组 nums
,它只包含 正 整数。
你的任务是通过进行以下操作 任意次(可以是 0 次)最小化 nums
的长度:
- 在
nums
中选择 两个不同 的下标i
和j
,满足nums[i] > 0
且nums[j] > 0
。 - 将结果
nums[i] % nums[j]
插入 nums 的结尾。 - 将
nums
中下标为i
和j
的元素删除。
请你返回一个整数,它表示进行任意次操作以后 nums
的 最小长度。
样例
输入:nums = [1,4,3,1]
输出:1
解释:使数组长度最小的一种方法是:
操作 1:选择下标 2 和 1,插入 nums[2] % nums[1] 到数组末尾,
得到 [1,4,3,1,3],然后删除下标为 2 和 1 的元素。
nums 变为 [1,1,3]。
操作 2:选择下标 1 和 2,插入 nums[1] % nums[2] 到数组末尾,
得到 [1,1,3,1],然后删除下标为 1 和 2 的元素。
nums 变为 [1,1]。
操作 3:选择下标 1 和 0,插入 nums[1] % nums[0] 到数组末尾,
得到 [1,1,0],然后删除下标为 1 和 0 的元素。
nums 变为 [0]。
nums 的长度无法进一步减小,所以答案为 1。
1 是可以得到的最小长度。
输入:nums = [5,5,5,10,5]
输出:2
解释:使数组长度最小的一种方法是:
操作 1:选择下标 0 和 3,插入 nums[0] % nums[3] 到数组末尾,
得到 [5,5,5,10,5,5],然后删除下标为 0 和 3 的元素。
nums 变为 [5,5,5,5]。
操作 2:选择下标 2 和 3,插入 nums[2] % nums[3] 到数组末尾,
得到 [5,5,5,5,0],然后删除下标为 2 和 3 的元素。
nums 变为 [5,5,0]。
操作 3:选择下标 0 和 1,插入 nums[0] % nums[1] 到数组末尾,
得到 [5,5,0,0],然后删除下标为 0 和 1 的元素。
nums 变为 [0,0]。
nums 的长度无法进一步减小,所以答案为 2。
2 是可以得到的最小长度。
输入:nums = [2,3,4]
输出:1
解释:使数组长度最小的一种方法是:
操作 1:选择下标 1 和 2,插入 nums[1] % nums[2] 到数组末尾,
得到 [2,3,4,3],然后删除下标为 1 和 2 的元素。
nums 变为 [2,3]。
操作 2:选择下标 1 和 0,插入 nums[1] % nums[0] 到数组末尾,
得到 [2,3,1],然后删除下标为 1 和 0 的元素。
nums 变为 [1]。
nums 的长度无法进一步减小,所以答案为 1。
1 是可以得到的最小长度。
限制
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
算法
(思维题) $O(n)$
- 考虑数组中的最小值 $mi$ 和最小值的出现次数 $cnt$。
- 如果存在一个不是最小值的数字,且模 $mi$ 不为 $0$,则可以直接利用这两个的模值当做唯一的最小值,可以利用这个最小值消掉所有其他数字,返回 $1$。
- 如果不存在,则返回 $cnt$ 除以 $2$ 上取整。
时间复杂度
- 遍历数组两次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minimumArrayLength(vector<int>& nums) {
const int n = nums.size();
int mi = nums[0], cnt = 1;
for (int i = 1; i < n; i++)
if (nums[i] < mi) {
mi = nums[i];
cnt = 1;
} else if (nums[i] == mi) {
++cnt;
}
for (int i = 0; i < n; i++)
if (nums[i] % mi != 0)
return 1;
return (cnt + 1) / 2;
}
};