同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个下标从 0 开始的整数数组 nums
,它只包含 正 整数。
你的任务是通过进行以下操作 任意次 (可以是 0 次) 最小化 nums
的长度:
nums
中选择 两个不同 的下标 i
和 j
,满足 nums[i] > 0
且 nums[j] > 0
。nums[i] % nums[j]
插入 nums
的结尾。nums
中下标为 i
和 j
的元素删除。请你返回一个整数,它表示进行任意次操作以后 nums
的 最小长度 。
示例 1:
输入: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 是可以得到的最小长度。
示例 2:
输入: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 是可以得到的最小长度。
示例 3:
输入: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 <= 105
1 <= nums[i] <= 109
我们不妨记数组 $nums$ 的最小的元素为 $mi$。
如果 $mi$ 只出现一次,那么我们将 $mi$ 与数组 $nums$ 的其他元素进行操作,可以将其他元素全部消去,最终剩下 $mi$ 一个元素,答案为 $1$。
如果 $mi$ 出现多次,我们判断数组 $nums$ 中的元素是否都是 $mi$ 的倍数。如果不是,即存在至少一个元素 $x$,使得 $0 \lt x \bmod mi \lt mi$,说明我们可以通过操作,构造出一个小于 $mi$ 的元素,那么这个小于 $mi$ 的元素与其他元素进行操作,可以将其他元素全部消去,最终剩下这个小于 $mi$ 的元素,答案为 $1$;如果都是 $mi$ 的倍数,我们可以先借助 $mi$,将所有大于 $mi$ 的元素消去,最终剩下的元素都是 $mi$,个数为 $cnt$,两两配对,每两个元素进行一次操作,最终剩下 $\lceil cnt / 2 \rceil$ 个元素,答案为 $\lceil cnt / 2 \rceil$。
时间复杂度 $O(n)$,其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。
class Solution:
def minimumArrayLength(self, nums: List[int]) -> int:
mi = min(nums)
if any(x % mi for x in nums):
return 1
return (nums.count(mi) + 1) // 2
class Solution {
public int minimumArrayLength(int[] nums) {
int mi = Arrays.stream(nums).min().getAsInt();
int cnt = 0;
for (int x : nums) {
if (x % mi != 0) {
return 1;
}
if (x == mi) {
++cnt;
}
}
return (cnt + 1) / 2;
}
}
class Solution {
public:
int minimumArrayLength(vector<int>& nums) {
int mi = *min_element(nums.begin(), nums.end());
int cnt = 0;
for (int x : nums) {
if (x % mi) {
return 1;
}
cnt += x == mi;
}
return (cnt + 1) / 2;
}
};
func minimumArrayLength(nums []int) int {
mi := slices.Min(nums)
cnt := 0
for _, x := range nums {
if x%mi != 0 {
return 1
}
if x == mi {
cnt++
}
}
return (cnt + 1) / 2
}
function minimumArrayLength(nums: number[]): number {
const mi = Math.min(...nums);
let cnt = 0;
for (const x of nums) {
if (x % mi) {
return 1;
}
if (x === mi) {
++cnt;
}
}
return (cnt + 1) >> 1;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。