2025-05-17：使数组非递减的最少除法操作次数。用go语言，给定一个整数数组 nums。定义：对于一个正整数 x，所有严

福大大架构师每日一题

发布于 2025-05-17 14:01:10

1140

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-05-17：使数组非递减的最少除法操作次数。用go语言，给定一个整数数组 nums。

定义：对于一个正整数 x，所有严格小于 x 的正因子称为 x 的“真因数”。举例来说，2 是 4 的真因数，但对于 6 来说，6 本身则不是它的真因数。

你可以对数组中的元素进行多次操作。每次操作中，选择数组中的某个元素，将它除以该元素的最大真因数。

目标是通过若干次操作，使得最终数组元素按照非递减顺序排列。

请你计算完成此目标所需的最少操作次数，如果无法实现，请返回 -1。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000。

输入：nums = [25,7]。

输出：1。

解释：

通过一次操作，25 除以 5 ，nums 变为 [5, 7] 。

题目来自3226。

分步骤描述过程：

1. 预处理最小质因数（LPF）数组：
- • 初始化一个大小为1,000,001的数组lpf，用于存储每个数的最小质因数（Least Prime Factor）。
- • 遍历从2到1,000,000的每个数i：
  - • 如果lpf[i]为0，说明i是质数。
  - • 对于每个质数i，遍历其所有倍数j（即j = i, 2i, 3i, ...），如果lpf[j]尚未被赋值，则将其设为i。这样lpf[j]就是j的最小质因数。
- • 预处理完成后，lpf[x]表示x的最小质因数。例如，lpf[25] = 5，lpf[7] = 7。
2. 处理数组nums：
- • 从数组的倒数第二个元素开始向前遍历（即从右向左遍历）：
  - • 对于当前元素nums[i]，如果它比后一个元素nums[i+1]大，则需要通过操作将其减小到不超过nums[i+1]。
  - • 操作的定义是将nums[i]除以其最大真因数。最大真因数可以通过nums[i] / lpf[nums[i]]得到（因为nums[i]的最小质因数lpf[nums[i]]对应其最小真因数，而最大真因数是nums[i] / lpf[nums[i]]）。
  - • 执行操作：nums[i] = lpf[nums[i]]（即nums[i]被替换为其最小质因数）。
  - • 操作次数ans加1。
  - • 如果操作后的nums[i]仍然大于nums[i+1]，则无法使数组非递减，直接返回-1。
- • 如果遍历完成后没有无法满足非递减的情况，返回操作次数ans。
3. 示例分析：
- • 输入nums = [25, 7]：
  - • 从i = 0开始（因为数组长度为2，i从len(nums)-2=0开始）。
  - • nums[0] = 25比nums[1] = 7大，需要进行操作。
  - • lpf[25] = 5，所以nums[0]被替换为5，操作次数ans变为1。
  - • 操作后数组为[5, 7]，此时5 <= 7，满足非递减。
  - • 返回操作次数1。

时间复杂度和空间复杂度：

1. 时间复杂度：
- • 预处理lpf数组：使用埃拉托斯特尼筛法的变种，时间复杂度为O(mx log log mx)，其中mx = 1,000,001。这是一个近似线性的时间复杂度。
- • 处理nums数组：遍历数组一次，每次操作的时间复杂度为O(1)（因为lpf数组是预处理的），所以总时间复杂度为O(n)，其中n是数组长度。
- • 总时间复杂度：O(mx log log mx + n)。由于mx是常数（1,000,001），可以简化为O(n)。
2. 空间复杂度：
- • lpf数组的大小为mx，即O(mx)。
- • 其他变量（如ans等）占用常数空间。
- • 总空间复杂度：O(mx)，即O(1,000,001)，是常数空间。

总结：

• 预处理lpf数组是关键，它使得后续操作可以在常数时间内完成。
• 通过从右向左遍历数组，可以贪心地处理每个元素，确保每次操作都是必要的。
• 时间复杂度和空间复杂度都是线性的，但由于mx是固定的，实际表现非常高效。

Go完整代码如下：

package main

import (
    "fmt"
)

const mx = 1_000_001

var lpf = [mx]int{}

func init() {
    for i := 2; i < mx; i++ {
        if lpf[i] == 0 {
            for j := i; j < mx; j += i {
                if lpf[j] == 0 {
                    lpf[j] = i
                }
            }
        }
    }
}

func minOperations(nums []int) (ans int) {
    for i := len(nums) - 2; i >= 0; i-- {
        if nums[i] > nums[i+1] {
            nums[i] = lpf[nums[i]]
            if nums[i] > nums[i+1] {
                return-1
            }
            ans++
        }
    }
    return
}

func main() {
    nums := []int{25, 7}
    result := minOperations(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

mx = 1_000_001
lpf = [0] * mx

definit():
    for i inrange(2, mx):
        if lpf[i] == 0:
            for j inrange(i, mx, i):
                if lpf[j] == 0:
                    lpf[j] = i

defmin_operations(nums):
    ans = 0
    for i inrange(len(nums) - 2, -1, -1):
        if nums[i] > nums[i + 1]:
            nums[i] = lpf[nums[i]]
            if nums[i] > nums[i + 1]:
                return -1
            ans += 1
    return ans

if __name__ == '__main__':
    init()
    nums = [25, 7]
    result = min_operations(nums)
    print(result)

Rust完整代码如下：

const MX: usize = 1_000_001;

fninit_lpf() ->Vec<usize> {
    letmut lpf = vec![0; MX];
    foriin2..MX {
        if lpf[i] == 0 {
            letmut j = i;
            while j < MX {
                if lpf[j] == 0 {
                    lpf[j] = i;
                }
                j += i;
            }
        }
    }
    lpf
}

fnmin_operations(nums: &mut [usize], lpf: &[usize]) ->i32 {
    letmut ans = 0;
    foriin (0..nums.len() - 1).rev() {
        if nums[i] > nums[i + 1] {
            nums[i] = lpf[nums[i]];
            if nums[i] > nums[i + 1] {
                return -1;
            }
            ans += 1;
        }
    }
    ans
}

fnmain() {
    letlpf = init_lpf();
    letmut nums = vec![25, 7];
    letresult = min_operations(&mut nums, &lpf);
    println!("{}", result);
}