【模拟】【C++算法】2826. 将三个组排序

简介: 【模拟】【C++算法】2826. 将三个组排序

LeetCode2826. 将三个组排序

给你一个下标从 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 <= 100

1 <= nums[i] <= 3

模拟

由于性能要求并不高,故可以直接模拟,枚举i,j 使得nums[0,i) 是第一组,nums[i,j)是第二组,nums[j,n)是第三组。

注意边界情况:写测试用例的时候,补充1组为空的三种情况,2组为空的三种情况。

代码

核心代码

class Solution {
public:
  int minimumOperations(vector<int>& nums) {
    m_c = nums.size();
    //[0,i) [i,j) [j,n)
    int iRet = m_c;
    for (int i = 0; i <= m_c; i++)
    {
      for (int j = i; j <= m_c; j++)
      {
        int cur = 0;
        for (int k = 0; k < i; k++)
        {
          cur += (nums[k] != 1);
        }
        for (int k = i; k < j; k++)
        {
          cur += (nums[k] != 2);
        }
        for (int k = j ; k < m_c; k++)
        {
          cur += (nums[k] != 3);
        }
        iRet = min(iRet, cur);
      }
    }
    return iRet;
  }
  int m_c;
};


扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业
。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法用**C++**实现。

相关文章
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
98 8
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
111 7
|
2月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
671 0
高精度算法(加、减、乘、除,使用c++实现)
|
2月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
41 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
45 0
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
34 0
|
2月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
81 0
|
2月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
2月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)