Medium

题目描述

给你一个整数数组 nums。

自然数 x 的任何严格小于 x 的正因数都称为 x 的真因数。例如，2 是 4 的真因数，而 6 不是 6 的真因数。

你可以对 nums 执行任意次数的操作，每次操作中你可以选择 nums 中的任一元素，将其除以它的最大真因数。

返回使数组变为非递减所需的最小操作次数。

如果无法通过任意次数的操作使数组变为非递减，返回 -1。

示例 1：

输入：nums = [25,7]
输出：1
解释：
使用一次操作，25 被 5 整除，nums 变为 [5, 7]。

示例 2：

输入：nums = [7,7,6]
输出：-1

示例 3：

输入：nums = [1,1,1,1]
输出：0

约束条件：

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

解题思路

解题思路

这道题的关键在于理解操作的本质：将一个数除以其最大真因数，实际上是将其缩小到最小质因数。

核心观察：

  1. 对于一个合数，其最大真因数是除了自身外最大的因数
  2. 当数字 x 除以其最大真因数时，结果是 x 的最小质因数
  3. 质数只能保持不变，因为质数没有真因数

算法思路：

  1. 从右往左遍历数组，这样可以确保当前元素知道右边的限制
  2. 对于每个位置，如果当前数字大于右边的数字，就需要进行操作
  3. 通过预处理找到每个数的最小质因数，这样可以快速计算操作结果
  4. 如果经过所有可能的操作后仍然无法满足非递减条件，返回-1

预处理优化： 使用埃拉托斯特尼筛法的变种来预处理每个数的最小质因数，这样可以在O(1)时间内获得操作后的结果。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int maxVal = *max_element(nums.begin(), nums.end());
        
        // 预处理每个数的最小质因数
        vector<int> minPrimeFactor(maxVal + 1);
        for (int i = 0; i <= maxVal; i++) minPrimeFactor[i] = i;
        
        for (int i = 2; i * i <= maxVal; i++) {
            if (minPrimeFactor[i] == i) { // i是质数
                for (int j = i * i; j <= maxVal; j += i) {
                    if (minPrimeFactor[j] == j) {
                        minPrimeFactor[j] = i;
                    }
                }
            }
        }
        
        int operations = 0;
        
        // 从右往左遍历
        for (int i = n - 2; i >= 0; i--) {
            while (nums[i] > nums[i + 1]) {
                int newVal = minPrimeFactor[nums[i]];
                if (newVal == nums[i]) {
                    // nums[i]是质数，无法再减小
                    return -1;
                }
                nums[i] = newVal;
                operations++;
            }
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        max_val = max(nums)
        
        # 预处理每个数的最小质因数
        min_prime_factor = list(range(max_val + 1))
        
        for i in range(2, int(max_val**0.5) + 1):
            if min_prime_factor[i] == i:  # i是质数
                for j in range(i * i, max_val + 1, i):
                    if min_prime_factor[j] == j:
                        min_prime_factor[j] = i
        
        operations = 0
        
        # 从右往左遍历
        for i in range(n - 2, -1, -1):
            while nums[i] > nums[i + 1]:
                new_val = min_prime_factor[nums[i]]
                if new_val == nums[i]:
                    # nums[i]是质数，无法再减小
                    return -1
                nums[i] = new_val
                operations += 1
        
        return operations

public class Solution {
    public int MinOperations(int[] nums) {
        int n = nums.Length;
        int maxVal = nums.Max();
        
        // 预处理每个数的最小质因数
        int[] minPrimeFactor = new int[maxVal + 1];
        for (int i = 0; i <= maxVal; i++) minPrimeFactor[i] = i;
        
        for (int i = 2; i * i <= maxVal; i++) {
            if (minPrimeFactor[i] == i) { // i是质数
                for (int j = i * i; j <= maxVal; j += i) {
                    if (minPrimeFactor[j] == j) {
                        minPrimeFactor[j] = i;
                    }
                }
            }
        }
        
        int operations = 0;
        
        // 从右往左遍历
        for (int i = n - 2; i >= 0; i--) {
            while (nums[i] > nums[i + 1]) {
                int newVal = minPrimeFactor[nums[i]];
                if (newVal == nums[i]) {
                    // nums[i]是质数，无法再减小
                    return -1;
                }
                nums[i] = newVal;
                operations++;
            }
        }
        
        return operations;
    }
}

var minOperations = function(nums) {
    const n = nums.length;
    const maxVal = Math.max(...nums);
    
    // 预处理每个数的最小质因数
    const minPrimeFactor = Array.from({length: maxVal + 1}, (_, i) => i);
    
    for (let i = 2; i * i <= maxVal; i++) {
        if (minPrimeFactor[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(M log log M + n × log M)M 是数组最大值，预处理筛法需要 O(M log log M)，主循环最坏情况每个数需要 O(log M) 次操作
空间复杂度O(M)需要额外数组存储最小质因数

相关题目