2826-将三个组排序

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

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

从 0 到 n - 1 的数字被分为编号从 1 到 3 的三个组，数字 i 属于组 nums[i] 。注意，有的组可能是
空的 。

你可以执行以下操作任意次：

  • 选择数字 x 并改变它的组。更正式的，你可以将 nums[x] 改为数字 1 到 3 中的任意一个。

你将按照以下过程构建一个新的数组 res ：

  1. 将每个组中的数字分别排序。
  2. 将组 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 <= 100
  • 1 <= nums[i] <= 3

请看 视频讲解 第三题。

方法一：最长非递减子序列

转换成最多可以保留多少个元素不变。这些保留的元素必须是非递减的，请看 最长递增子序列【基础算法精讲 20】 ，视频末尾讲了如何处理非递减的情况。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
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)
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minimumOperations(List<Integer> nums) {
        List<Integer> g = new ArrayList<>();
        for (int x : nums) {
            int j = upperBound(g, x);
            if (j == g.size()) g.add(x);
            else g.set(j, x);
        }
        return nums.size() - g.size();
    }

    // 开区间写法
    private int upperBound(List<Integer> g, int target) {
        int left = -1, right = g.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] <= target
            // nums[right] > target
            int mid = (left + right) >>> 1;
            if (g.get(mid) <= target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minimumOperations(vector<int> &nums) {
        vector<int> g;
        for (int x : nums) {
            auto it = upper_bound(g.begin(), g.end(), x);
            if (it == g.end()) g.push_back(x);
            else *it = x;
        }
        return nums.size() - g.size();
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
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)
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n\log n)，其中 n 为 nums 的长度。
  • 空间复杂度：\mathcal{O}(n)。

方法二：状态机 DP

请看【基础算法精讲 21】 。

定义 f[i+1][j] 表示考虑 nums}[0] 到 nums}[i]，且 nums}[i] 变成 j 的最小修改次数。

枚举第 i-1 个数改成了 k，有

f[i+1][j] = \min_{1\le k\le j} f[i][k] + [j \ne \textit{nums}[i]]

初始值 f[0][j] = 0。

答案为 \min(f[n])。

代码实现时，第一个维度可以省略。为了避免状态被覆盖，需要倒序枚举 j。

[sol-Python3]
1
2
3
4
5
6
7
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:])
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
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);
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 }

也可以计算至多保留多少个元素：

f[j] = \max(f[j], f[j-1]) + [j = \textit{nums}[i]]

[sol-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        f = [0] * 4
        for x in nums:
            f[x] += 1
            f[2] = max(f[2], f[1])
            f[3] = max(f[3], f[2])
        return len(nums) - max(f)
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int minimumOperations(List<Integer> nums) {
        var f = new int[4];
        for (int x : nums) {
            f[x]++;
            f[2] = Math.max(f[2], f[1]);
            f[3] = Math.max(f[3], f[2]);
        }
        return nums.size() - Math.max(Math.max(f[1], f[2]), f[3]);
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minimumOperations(vector<int> &nums) {
        int f[4]{};
        for (int x: nums) {
            f[x]++;
            f[2] = max(f[2], f[1]);
            f[3] = max(f[3], f[2]);
        }
        return nums.size() - *max_element(f + 1, f + 4);
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
func minimumOperations(nums []int) int {
	f := [4]int{}
	for _, x := range nums {
		f[x]++
		f[2] = max(f[2], f[1])
		f[3] = max(f[3], f[2])
	}
	return len(nums) - max(max(f[1], f[2]), f[3])
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
  • 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。
 Comments
On this page
2826-将三个组排序
  1. 方法一：最长非递减子序列
  2. 方法二：状态机 DP