通过操作使数组长度最小

难度: Medium

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 42 ms

内存: 28.0 MB

class Solution:
    def minimumArrayLength(self, nums: List[int]) -> int:
        m = min(nums)
        for x in nums:
            if x % m:
                return 1
        return (nums.count(m) + 1) // 2

Explain

题解的核心思路是利用模运算的性质来最小化数组长度。首先找到数组中的最小值m，因为任何数x与m取模，结果必然在0到m-1之间。如果数组中任何一个数x满足x % m不为0，那么我们可以通过合适的操作使数组长度最终减少至1（因为这些操作会生成比m小的新数，继续进行操作最终可能达到1）。如果所有数x都满足x % m为0（即所有数都是m的倍数），那么数组长度最小化的关键在于m的个数。因为每次操作可以减少两个m，最后可能剩下一个m或不剩。具体来说，如果m的个数是奇数，最后会剩一个m，是偶数则不剩。因此，返回值应该是(m的个数 + 1) // 2。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumArrayLength(self, nums: List[int]) -> int:
        # 找到数组中的最小值m
        m = min(nums)
        # 检查数组中是否有元素不是m的倍数
        for x in nums:
            if x % m:
                return 1  # 如果找到，则可以通过操作最终使数组长度为1
        # 如果所有元素都是m的倍数，则结果取决于m的个数
        return (nums.count(m) + 1) // 2  # 计算m的个数，根据奇偶返回1或0

Explore

在题解中，当所有元素都是最小值m的倍数时，我们可以通过每次操作删除两个m来减少数组的长度。具体操作是，选择数组中任意两个m，然后将他们从数组中移除。这个过程重复进行，直到不能再进行为止。如果m的个数是奇数，操作结束时会剩下一个m；如果是偶数，最后一个操作会将最后两个m同时移除，从而数组长度为0。通过这种方式，可以确保数组长度达到可能的最小值。

题解的算法确保如果数组中存在至少一个非m倍数的元素，那么数组长度可以通过操作减至1。这是因为非m倍数的元素经过取模运算后会产生一个小于m的余数，而这个余数再与其他元素进行取模操作，理论上可以通过连续操作最终得到1。因此，该方法在理论上总是能保证数组长度减至1，除非所有元素均为m的倍数。

在实际操作中，选择i和j的原则是确保每次操作都能产生一个新的数值，从而有机会减少数组中不同数值的总数。通常，选择不同的元素i和j，计算i % j或j % i，并用结果替换较大的数值。这样的操作会持续减少数组中较大数值的出现，从而逐步减少数组长度。关键在于每次都选择能产生新数值的i和j，这通常是选择两个不同的数值进行操作。

当所有元素都是m的倍数且m的数量是偶数时，通过重复删除操作，可以将数组中的所有元素完全去除，最终数组长度为0。这种情况在题解的逻辑中是合理的，并与题目的要求一致，即通过操作使数组长度尽可能小。如果m的数量是奇数，则无法完全删除所有元素，将会剩下一个m，因此数组长度为1。