2366-将数组排序的最少替换次数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个下标从 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 <= 105
  • 1 <= nums[i] <= 109

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

提示 1

每个数字要么不变，要么分成更小的数字。

提示 2

最后一个数字需要操作吗？

不需要，如果操作，前面的数字就需要变得更小，这会让操作次数增多。

提示 3

倒着遍历 nums。设当前操作出的最小值为 m，如果 nums}[i]>m，那么需要拆分 nums}[i]，使得拆分出的数字的最大值不超过 m。

设拆分出了 x 个数字，由于这 x 个数字都不超过 m，即

\textit{nums}[i] = v_1+v_2+\cdots+v_x \le m+m+\cdots+m = mx

得

x\ge\left\lceil\dfrac{\textit{nums}[i]}{m}\right\rceil

为了使操作次数尽量小，应取等号，即

x=\left\lceil\dfrac{\textit{nums}[i]}{m}\right\rceil

操作次数为 k=x-1。

为了使拆分出的数字的最小值尽可能地大，拆分出的最小数字应为 \left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor，证明如下：

若这 x 个数均为 \left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor，那么有

x\left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor\le \textit{nums}[i]

若这 x 个数均为 \left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor+1，那么有

x\left(\left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor+1\right)\ge x\left\lceil\dfrac{\textit{nums}[i]}{x}\right\rceil \ge \textit{nums}[i]

联合得到

x\left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor\le \textit{nums}[i]\le x\left(\left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor+1\right)

据此，我们可以给出一个拆分方案：将这 x 个数均初始化为 \left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor，然后给其中的 nums}[i]-x\left\lfloor\dfrac{\textit{nums}[i]}{x}\right\rfloor 个数字加一，这样可以使这 x 数的和恰好为 nums}[i]。上面的不等式说明这样的方案是存在的。

代码实现时，无需判断 nums}[i] 与 m 的大小关系。

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)，仅用到若干额外变量。
[sol1-Python3]
1
2
3
4
5
6
7
8
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
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
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
}

思考题

每个数字需要拆分成若干整数（目前题目没有说清楚这一点，读者可以通过测试 [5,5,3] 这个输入来确认，预期结果为 3）。

如果可以拆分成实数，答案会是多少呢？比如 [5,5,3] 可以拆分成 [2.5,2.5,2.5,2.5,3]，答案为 2。

如何在计算过程中避免使用浮点数？

 Comments
On this page
2366-将数组排序的最少替换次数