Medium

题目描述

给定一个包含正整数的 0 索引整数数组 nums。

你的任务是通过执行以下操作任意次数（包括零次）来最小化 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。

示例 2：

输入：nums = [5,5,5,10,5]
输出：2

示例 3：

输入：nums = [2,3,4]
输出：1

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这道题的关键在于理解操作的本质：每次操作将两个数替换为它们的取模结果，这实际上是在执行类似欧几里德算法的过程。

我们需要分析几种情况：

  1. 最小值只出现一次：设最小值为 x，如果 x 只出现一次，那么我们可以将所有其他数 y 与 x 进行操作。由于 x < y，所以 x % y = x，这样我们可以消除所有大于 x 的数，最终只剩下 x，答案为 1。

  2. 存在数字 y 使得 y % min_val ≠ 0：如果存在这样的数字，那么 y % min_val 会产生一个比 min_val 更小的数，回到情况 1，答案为 1。

  3. 所有数字都是最小值的倍数，且最小值出现多次：在这种情况下，我们只能将相同的最小值配对，每次操作消除 2 个数字（因为 min_val % min_val = 0）。如果最小值出现 cnt 次，最终长度为 ⌈cnt/2⌉。

算法步骤：

  1. 找到数组中的最小值
  2. 统计最小值的出现次数
  3. 检查是否存在不能被最小值整除的数
  4. 根据上述三种情况返回相应结果

代码实现

class Solution {
public:
    int minimumArrayLength(vector<int>& nums) {
        int min_val = *min_element(nums.begin(), nums.end());
        int count = 0;
        
        for (int num : nums) {
            if (num == min_val) {
                count++;
            } else if (num % min_val != 0) {
                return 1;
            }
        }
        
        return (count + 1) / 2;
    }
};

class Solution:
    def minimumArrayLength(self, nums: List[int]) -> int:
        min_val = min(nums)
        count = 0
        
        for num in nums:
            if num == min_val:
                count += 1
            elif num % min_val != 0:
                return 1
        
        return (count + 1) // 2

public class Solution {
    public int MinimumArrayLength(int[] nums) {
        int minVal = nums.Min();
        int count = 0;
        
        foreach (int num in nums) {
            if (num == minVal) {
                count++;
            } else if (num % minVal != 0) {
                return 1;
            }
        }
        
        return (count + 1) / 2;
    }
}

var minimumArrayLength = function(nums) {
    const minVal = Math.min(...nums);
    
    // Check if any element can reduce minVal further
    for (let num of nums) {
        if (num !== minVal && num % minVal !== 0) {
            return 1;
        }
    }
    
    // Count occurrences of minimum value
    const count = nums.filter(x => x === minVal).length;
    return Math.ceil(count / 2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(1)

时间复杂度：需要遍历数组两次，一次找最小值，一次统计和检查，总体为 O(n)。 空间复杂度：只使用了常数个额外变量，为 O(1)。