sorting-three-groups

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code>. Each element in <code>nums</code> is 1, 2 or 3. In each operation, you can remove an element from&nbsp;<code>nums</code>. Return the minimum number of operations to make <code>nums</code> non-decreasing.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [2,1,3,2,1]

Output: 3

Explanation:

One of the optimal solutions is to remove <code>nums[0]</code>, <code>nums[2]</code> and <code>nums[3]</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [1,3,2,1,3,3]

Output: 2

Explanation:

One of the optimal solutions is to remove <code>nums[1]</code> and <code>nums[2]</code>.
</div>

Example 3:

<div class="example-block">
Input: nums = [2,2,2,2,3,3]

Output: 0

Explanation:

<code>nums</code> is already non-decreasing.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 3</code></li>
</ul>

&nbsp;
Follow-up: Can you come up with an algorithm that runs in <code>O(n)</code> time complexity?

第 111 场双周赛

biweekly-contest-111

minimumOperations

资深工程师

Sorting Three Groups

Array

Binary Search

Dynamic Programming

给你一个整数数组&nbsp;<code>nums</code>&nbsp;。<code>nums</code>&nbsp;的每个元素是 1，2 或 3。在每次操作中，你可以删除&nbsp;<code>nums</code>&nbsp;中的一个元素。返回使 nums 成为 非递减&nbsp;顺序所需操作数的 最小值。

&nbsp;

示例 1：

<pre>
输入：nums = [2,1,3,2,1]
输出：3
解释：
其中一个最优方案是删除 nums[0]，nums[2] 和 nums[3]。
</pre>

示例 2：

<pre>
输入：nums = [1,3,2,1,3,3]
输出：2
解释：
其中一个最优方案是删除 nums[1] 和 nums[2]。
</pre>

示例 3：

<pre>
输入：nums = [2,2,2,2,3,3]
输出：0
解释：
nums 已是非递减顺序的。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 3</code></li>
</ul>

进阶：你可以使用&nbsp;<code>O(n)</code>&nbsp;时间复杂度以内的算法解决吗？