将三个组排序

You are given a 0-indexed integer array nums of length n.

The numbers from 0 to n - 1 are divided into three groups numbered from 1 to 3, where number i belongs to group nums[i]. Notice that some groups may be empty.

You are allowed to perform this operation any number of times:

• Pick number x and change its group. More formally, change nums[x] to any number from 1 to 3.

A new array res is constructed using the following procedure:

1. Sort the numbers in each group independently.
2. Append the elements of groups 1, 2, and 3 to res in this order.

Array nums is called a beautiful array if the constructed array res is sorted in non-decreasing order.

Return the minimum number of operations to make nums a beautiful array.

 

Example 1:

Input: nums = [2,1,3,2,1]
Output: 3
Explanation: It's optimal to perform three operations:
1. change nums[0] to 1.
2. change nums[2] to 1.
3. change nums[3] to 1.
After performing the operations and sorting the numbers in each group, group 1 becomes equal to [0,1,2,3,4] and group 2 and group 3 become empty. Hence, res is equal to [0,1,2,3,4] which is sorted in non-decreasing order.
It can be proven that there is no valid sequence of less than three operations.

Example 2:

Input: nums = [1,3,2,1,3,3]
Output: 2
Explanation: It's optimal to perform two operations:
1. change nums[1] to 1.
2. change nums[2] to 1.
After performing the operations and sorting the numbers in each group, group 1 becomes equal to [0,1,2,3], group 2 becomes empty, and group 3 becomes equal to [4,5]. Hence, res is equal to [0,1,2,3,4,5] which is sorted in non-decreasing order.
It can be proven that there is no valid sequence of less than two operations.

Example 3:

Input: nums = [2,2,2,2,3,3]
Output: 0
Explanation: It's optimal to not perform operations.
After sorting the numbers in each group, group 1 becomes empty, group 2 becomes equal to [0,1,2,3] and group 3 becomes equal to [4,5]. Hence, res is equal to [0,1,2,3,4,5] which is sorted in non-decreasing order.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 3

// Java Stream solution
// 思路：
// 1. 使用stream计算每个组的元素数量。
// 2. 计算最小操作次数。
// 3. 使用stream简化代码。

import java.util.Arrays;

public class Solution {
    public int minSteps(int[] nums) {
        long count1 = Arrays.stream(nums).filter(num -> num == 1).count();
        long count2 = Arrays.stream(nums).filter(num -> num == 2).count();
        long count3 = Arrays.stream(nums).filter(num -> num == 3).count();
        long maxCount = Math.max(count1, Math.max(count2, count3));
        return (int)(nums.length - maxCount);
    }
}

该题解采用动态规划来解决问题。定义一个dp数组，其中dp[j]表示将数组nums的前i个元素调整成j+1组的最小操作次数。对于每个元素nums[i]，根据它当前的值，更新下一个状态nxt。具体地，若nums[i]为1，则将其保持在组1是不需要操作的，而移动到组2或组3则至少需要一次操作。类似的逻辑应用于当nums[i]值为2或3时。通过遍历整个数组，不断更新dp数组，最后返回dp数组中的最小值，即为将整个数组调整到最终状态的最小操作次数。

O(n)

O(1)