golang 解法, 执行用时: 0 ms, 内存消耗: 17.1 MB, 提交时间: 2024-10-23 09:34:04

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
}

java 解法, 执行用时: 81 ms, 内存消耗: 67.5 MB, 提交时间: 2024-10-23 09:33:45

class Solution {
    private static final int MX = 1_000_001;
    private static final int[] lpf = new int[MX];

    static {
        for (int i = 2; i < MX; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j < MX; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }
    }

    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = nums.length - 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 ans;
    }
}

cpp 解法, 执行用时: 3 ms, 内存消耗: 142.3 MB, 提交时间: 2024-10-23 09:33:33

const int MX = 1'000'001;
int LPF[MX];

auto init = [] {
    for (int i = 2; i < MX; i++) {
        if (LPF[i] == 0) {
            for (int j = i; j < MX; j += i) {
                if (LPF[j] == 0) {
                    LPF[j] = i;
                }
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = nums.size() - 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 ans;
    }
};

python3 解法, 执行用时: 52 ms, 内存消耗: 38.6 MB, 提交时间: 2024-10-23 09:33:19

MX = 1_000_001
LPF = [0] * MX
for i in range(2, MX):
    if LPF[i] == 0:
        for j in range(i, MX, i):
            if LPF[j] == 0:
                LPF[j] = i

# 预处理，LPF(x) : x的最小质因子
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        for i in range(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