class Solution {
public:
int minOperations(vector<int>& nums) {
}
};
3326. 使数组非递减的最少除法操作次数
给你一个整数数组 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 <= 1051 <= nums[i] <= 106相似题目
原站题解
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