class Solution {
public:
long long minimumReplacement(vector<int>& nums) {
}
};
2366. 将数组排序的最少替换次数
给你一个下表从 0 开始的整数数组 nums 。每次操作中，你可以将数组中任何一个元素替换为 任意两个 和为该元素的数字。
nums = [5,6,7] 。一次操作中，我们可以将 nums[1] 替换成 2 和 4 ，将 nums 转变成 [5,2,4,7] 。请你执行上述操作，将数组变成元素按 非递减 顺序排列的数组，并返回所需的最少操作次数。
示例 1：
输入：nums = [3,9,3] 输出：2 解释：以下是将数组变成非递减顺序的步骤： - [3,9,3] ，将9 变成 3 和 6 ，得到数组 [3,3,6,3] - [3,3,6,3] ，将 6 变成 3 和 3 ，得到数组 [3,3,3,3,3] 总共需要 2 步将数组变成非递减有序，所以我们返回 2 。
示例 2：
输入：nums = [1,2,3,4,5] 输出：0 解释：数组已经是非递减顺序，所以我们返回 0 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109原站题解
rust 解法, 执行用时: 12 ms, 内存消耗: 4 MB, 提交时间: 2023-09-14 00:48:36
impl Solution {
pub fn minimum_replacement(mut nums: Vec<i32>) -> i64 {
nums.reverse();
let mut res = 0;
let mut a = nums[0];
for v in nums.iter().skip(1) {
if *v > a {
let x = (*v + a - 1) / a;
a = *v / x;
res += (x - 1) as i64;
} else {
a = *v
}
}
res
}
}
golang 解法, 执行用时: 92 ms, 内存消耗: 10.6 MB, 提交时间: 2023-09-14 00:48:22
func minimumReplacement(nums []int) (ans int64) {
m := nums[len(nums)-1]
for i := len(nums) - 2; i >= 0; i-- {
k := (nums[i] - 1) / m
ans += int64(k)
m = nums[i] / (k + 1)
}
return
}
cpp 解法, 执行用时: 140 ms, 内存消耗: 53.7 MB, 提交时间: 2023-09-14 00:48:07
class Solution {
public:
long long minimumReplacement(vector<int> &nums) {
long ans = 0L;
int m = nums.back();
for (int i = int(nums.size()) - 2; i >= 0; --i) {
int k = (nums[i] - 1) / m;
ans += k;
m = nums[i] / (k + 1);
}
return ans;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 53.2 MB, 提交时间: 2023-09-14 00:47:53
class Solution {
public long minimumReplacement(int[] nums) {
var ans = 0L;
var m = nums[nums.length - 1];
for (var i = nums.length - 2; i >= 0; --i) {
var k = (nums[i] - 1) / m;
ans += k;
m = nums[i] / (k + 1);
}
return ans;
}
}
python3 解法, 执行用时: 80 ms, 内存消耗: 29.2 MB, 提交时间: 2023-09-14 00:47:41
class Solution:
def minimumReplacement(self, nums: List[int]) -> int:
ans, m = 0, nums[-1]
for num in reversed(nums):
k = (num - 1) // m
ans += k
m = num // (k + 1)
return ans