class Solution {
public:
int minimumOperations(vector<int>& nums) {
}
};
6941. 将三个组排序
给你一个下标从 0 开始长度为 n 的整数数组 nums 。
从 0 到 n - 1 的数字被分为编号从 1 到 3 的三个组，数字 i 属于组 nums[i] 。注意，有的组可能是 空的 。
你可以执行以下操作任意次：
x 并改变它的组。更正式的，你可以将 nums[x] 改为数字 1 到 3 中的任意一个。你将按照以下过程构建一个新的数组 res ：
1 ，2 和 3 中的元素 依次 连接以得到 res 。如果得到的 res 是 非递减顺序的，那么我们称数组 nums 是 美丽数组 。
请你返回将 nums 变为 美丽数组 需要的最少步数。
示例 1：
输入：nums = [2,1,3,2,1] 输出：3 解释：以下三步操作是最优方案： 1. 将 nums[0] 变为 1 。 2. 将 nums[2] 变为 1 。 3. 将 nums[3] 变为 1 。 执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3,4] ，组 2 和组 3 都为空。所以 res 等于 [0,1,2,3,4] ，它是非递减顺序的。 三步操作是最少需要的步数。
示例 2：
输入：nums = [1,3,2,1,3,3] 输出：2 解释：以下两步操作是最优方案： 1. 将 nums[1] 变为 1 。 2. 将 nums[2] 变为 1 。 执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3] ，组 2 为空，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。 两步操作是最少需要的步数。
示例 3：
输入：nums = [2,2,2,2,3,3] 输出：0 解释：不需要执行任何操作。 组 1 为空，组 2 为 [0,1,2,3] ，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 3原站题解
golang 解法, 执行用时: 28 ms, 内存消耗: 6.5 MB, 提交时间: 2023-08-21 10:04:23
func minimumOperations(nums []int) int {
f := [4]int{}
for _, x := range nums {
for j := 3; j > 0; j-- {
for k := 1; k <= j; k++ {
f[j] = min(f[j], f[k])
}
if j != x {
f[j]++
}
}
}
ans := len(nums)
for _, v := range f[1:] {
ans = min(ans, v)
}
return ans
}
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 76 ms, 内存消耗: 85.6 MB, 提交时间: 2023-08-21 10:04:09
class Solution {
public:
int minimumOperations(vector<int> &nums) {
int f[4]{};
for (int x: nums)
for (int j = 3; j; j--)
f[j] = *min_element(f + 1, f + j + 1) + (j != x);
return *min_element(f + 1, f + 4);
}
};
java 解法, 执行用时: 5 ms, 内存消耗: 42.5 MB, 提交时间: 2023-08-21 10:03:55
class Solution {
public int minimumOperations(List<Integer> nums) {
var f = new int[4];
for (int x : nums) {
for (int j = 3; j > 0; j--) {
for (int k = 1; k <= j; k++)
f[j] = Math.min(f[j], f[k]);
if (j != x) f[j]++;
}
}
int ans = nums.size();
for (int j = 1; j < 4; j++)
ans = Math.min(ans, f[j]);
return ans;
}
}
python3 解法, 执行用时: 208 ms, 内存消耗: 16 MB, 提交时间: 2023-08-21 10:03:05
'''
定义 [i+1][j] 表示考虑 nums[0] 到 nums[i]，且 nums[i] 变成 j 的最小修改次数。
枚举第 i−1 个数改成了 k，有f[i+1][j]= 1≤k≤j min f[i][k]+[j<>nums[i]]
初始值 f[0][j]=0。答案为 min(f[n])。
代码实现时，第一个维度可以省略。为了避免状态被覆盖，需要倒序枚举 j。
'''
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
f = [0] * 4
for x in nums:
for j in range(3, 0, -1):
f[j] = min(f[k] for k in range(1, j + 1)) + (j != x)
return min(f[1:])
golang 解法, 执行用时: 16 ms, 内存消耗: 6.5 MB, 提交时间: 2023-08-21 09:59:56
func minimumOperations(nums []int) int {
g := []int{}
for _, x := range nums {
p := sort.SearchInts(g, x+1)
if p < len(g) {
g[p] = x
} else {
g = append(g, x)
}
}
return len(nums) - len(g)
}
python3 解法, 执行用时: 76 ms, 内存消耗: 15.9 MB, 提交时间: 2023-08-21 09:59:42
# 转换成最多可以保留多少个元素不变。这些保留的元素必须是非递减的，
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
g = []
for x in nums:
j = bisect_right(g, x)
if j == len(g):
g.append(x)
else:
g[j] = x
return len(nums) - len(g)