当前位置: 首页 > news >正文

【算法】分治:归并之 912.排序数组(medium)

系列专栏

双指针

模拟算法

分治思想


 

目录

1、题目链接

2、题目介绍

3、解法

解决方案选择

解题步骤

4、代码


1、题目链接

912. 排序数组 - 力扣(LeetCode)

2、题目介绍

给你一个整数数组 nums,请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n)),并且空间复杂度尽可能小。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

3、解法

解决方案选择

为了满足时间复杂度的要求,我们选择使用归并排序(Merge Sort)算法。归并排序是一种分而治之的算法,它将数组分成两半,递归地对它们进行排序,然后将结果合并成一个有序数组。这个过程的时间复杂度为 O(nlog(n)),因为它将问题分解成更小的子问题,直到子问题的大小为1(即已经排序),然后将它们合并起来。

解题步骤

  1. 定义辅助函数
    • merge 函数:负责将两个已排序的子数组合并成一个有序数组。它使用了一个临时数组 tmp 来存储合并过程中的元素,以避免在原始数组上进行复杂的元素移动。
    • mergeSort 函数:递归地将数组分成更小的部分,直到每个部分只包含一个元素(自然是有序的),然后调用 merge 函数将它们合并成有序数组。
  2. 归并排序过程
    • 拆分:通过递归调用 mergeSort,将数组不断拆分成更小的部分,直到每个部分只包含一个元素。
    • 合并:在递归返回的过程中,使用 merge 函数将相邻的两个已排序的子数组合并成一个有序数组。
  3. 空间复杂度
    • 归并排序的空间复杂度主要由临时数组 tmp 决定,其大小为 nums.size(),因此空间复杂度为 O(n)。
  4. 时间复杂度
    • 归并排序的时间复杂度为 O(nlog(n)),这主要是由于每次递归调用都将问题规模减半,并且合并操作的时间复杂度为 O(n)。

4、代码


class Solution {
public://归并排序//void merge(vector<int>& nums, vector<int>& tmp, int left, int mid, int right){int lsort = left, rsort = mid + 1;//两个需要进行合并区域的第一个元素下标int cur = left;//遍历tmp数组的计数器while (lsort <= mid && rsort <= right){if (nums[lsort] <= nums[rsort]){tmp[cur++] = nums[lsort++];}else {tmp[cur++] = nums[rsort++];}}//如果有剩余的数,没有参与比较,直接插入到tmp中while (lsort <= mid){tmp[cur++] = nums[lsort++];}while (rsort <= right)tmp[cur++] = nums[rsort++];while (left <= right){nums[left] = tmp[left];left++;}}//先拆分,再合并void mergeSort(vector<int>& nums, vector<int>& tmp, int left, int right){if (left < right){int mid = (right + left) / 2;mergeSort(nums, tmp, left, mid);mergeSort(nums, tmp, mid + 1, right);merge(nums, tmp, left, mid, right);}}vector<int> sortArray(vector<int>& nums) {vector<int> tmp(nums.size());mergeSort(nums, tmp, 0, nums.size() - 1);return nums;}
};

💗感谢阅读!💗

相关文章:

【算法】分治:归并之 912.排序数组(medium)

系列专栏 双指针 模拟算法 分治思想 目录 1、题目链接 2、题目介绍 3、解法 解决方案选择 解题步骤 4、代码 1、题目链接 912. 排序数组 - 力扣&#xff08;LeetCode&#xff09; 2、题目介绍 给你一个整数数组 nums&#xff0c;请你将该数组升序排列。 你必须在 …...

Cocos 3.8.3 实现外描边效果(逃课玩法)

本来想着用Cocos 的Shader Graph照搬Unity的思路来加外描边&#xff0c;发现不行&#xff0c;然后我就想弄两个物体不就行了吗&#xff0c;一个是放大的版本&#xff0c;再放大的版本上加一个材质&#xff0c;这个材质面剔除选择前面的面剔除就行了&#xff0c;果不其然还真行。…...

著名建筑物检测与识别系统源码分享

著名建筑物检测与识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Comp…...

使用php生成图片

可以用这方法生成图片 水印 字体可以在资源绑定下载&#xff0c;如果字体路径不对&#xff0c;则不会输出文字图片 public function generateImage($text,$id) { header("Cache-Control: no-cache, must-revalidate"); header("Expires: Mon, 26 Jul 1997 05:0…...

C++ 数据类型分类

在C中&#xff0c;数据类型可以大致分为内置类型&#xff08;Built-in Types&#xff09;、标准库类型&#xff08;Standard Library Types&#xff09;和自定义类型&#xff08;User-Defined Types&#xff09;三大类。 内置类型&#xff08;Built-in Types&#xff09; 内置…...

java安装更新jdk11后设置环境JAVA_HOME

背景,已经安装成功,但是环境还是java1.8 java -version openjdk version "11.0.23" 2024-04-16 LTS OpenJDK Runtime Environment (Red_Hat-11.0.23.0.9-2.el7_9) (build 11.0.23+9-LTS) OpenJDK 64-Bit Server VM (Red_Hat-11.0.23.0.9-2.el7_9) (build 11.0.…...

Java.动态代理

1.创建一个接口 package Mydynamicproxy1;public interface Star {public abstract String sing(String str);public abstract void dance(String str); }2.创建一个BigStar类&#xff0c;要实现Star这个接口 package Mydynamicproxy1;public class BigStar implements Star{…...

SpringBoot自定义异常

前言 在前后端开发中&#xff0c;后端接口返回的数据都是JSON格式的&#xff0c;但是后端可能会出现一些可以未知从异常&#xff0c;在后端抛出这些异常的时候&#xff0c;也需要返回相同格式的JSON数据&#xff0c;这时候就需要我们设置全局异常处理器。在后端开发中&#xf…...

华为源NAT技术与目的NAT技术

1&#xff09;源NAT对报文源地址进行转换&#xff0c;分为NAT NO-PAT&#xff0c;NAPT,EASY-IP,三元组NAT&#xff1b; &#xff08;1&#xff09;NAT NO-PAT原理&#xff1a; no-port address translation:非端口地址转换&#xff1a;只转换地址&#xff0c;不转换端口&…...

人工智能与机器学习原理精解【25】

文章目录 正则化概述一、正则化的种类二、正则化的定义三、正则化的计算四、正则化的性质五、正则化的例子 公式与计算一、正则化的种类Dropout正则化一、基本思想二、实现方法三、作用机制四、使用注意事项五、总结Dropout正则化的例子和公式。一、Dropout正则化的例子二、Dro…...

一篇文章讲清楚synchronized关键字的作用及原理

概述 在应用Sychronized关键字时需要把握如下注意点&#xff1a; 一把锁只能同时被一个线程获取&#xff0c;没有获得锁的线程只能等待&#xff1b; 每个实例都对应有自己的一把锁(this),不同实例之间互不影响&#xff1b;例外&#xff1a;锁对象是*.class以及synchronized修…...

深度学习模型之BERT的24个小模型源码与预训练紧凑模型的重要性

原始信息 论文&#xff1a; Well-Read Students Learn Better: On the Importance of Pre-training Compact Models作者&#xff1a;Iulia Turc, Ming-Wei Chang, Kenton Lee, Kristina Toutanova地址&#xff1a;arxiv.org/pdf/1908.08…中文&#xff1a;阅读良好的学生学得更…...

【HarmonyOS】深入理解@Observed装饰器和@ObjectLink装饰器:嵌套类对象属性变化

【HarmonyOS】深入理解Observed装饰器和ObjectLink装饰器&#xff1a;嵌套类对象属性变化 前言 之前就Observed和ObjectLink写过一篇讲解博客【HarmonyOS】 多层嵌套对象通过ObjectLink和Observed实现渲染更新处理&#xff01; 其中就Observe监听类的使用&#xff0c;Object…...

Java笔试面试题AI答之设计模式(1)

文章目录 1. 简述什么是设计模式 &#xff1f;2. 叙述常见Java设计模式分类 &#xff1f;3. Java 设计模式的六大原则 &#xff1f;4. 简述对 MVC 的理解&#xff0c; MVC 有什么优缺点&#xff1f;MVC 的三个核心部分&#xff1a;MVC 的优点&#xff1a;MVC 的缺点&#xff1a…...

java调用opencv部署到centos7

1、官网下载opencv https://opencv.org/releases/ 2、下载opencv并解压 unzip opencv-3.4.7.zip cd opencv-3.4.7 mkdir build cd build/ 3、安装cmake yum remove cmake -y ; yum install -y gcc gcc-c make automake openssl openssl-devel wget https://cmake.org/files/…...

【python qdrant 向量数据库 完整示例代码】

测试一下python版本的dqrant向量数据库的效果&#xff0c;完整代码如下&#xff1a; 安装库 !pip install qdrant-client>1.1.1 !pip install -U sentence-transformers导入 from qdrant_client import models, QdrantClient from sentence_transformers import SentenceT…...

初识C语言(三)

感兴趣的朋友们可以留个关注&#xff0c;我们共同交流&#xff0c;相互促进学习。 文章目录 前言 八、函数 九、数组 &#xff08;1&#xff09;数组的定义 &#xff08;2&#xff09;数组的下标和使用 十、操作符 &#xff08;1&#xff09;算数操作符 &#xff08;2&#xff…...

用通义灵码如何快速合理解决遗留代码问题?

本文首先介绍了遗留代码的概念&#xff0c;并对遗留代码进行了分类。针对不同类型的遗留代码&#xff0c;提供了相应的处理策略。此外&#xff0c;本文重点介绍了通义灵码在维护遗留代码过程中能提供哪些支持。 什么是遗留代码 与过时技术相关的代码&#xff1a; 与不再受支持的…...

新书推荐——《Python贝叶斯深度学习》

在过去的十年中&#xff0c;机器学习领域取得了长足的进步&#xff0c;并因此激发了公众的想象力。但我们必须记住&#xff0c;尽管这些算法令人印象深刻&#xff0c;但它们并非完美无缺。本书旨在通过平实的语言介绍如何在深度学习中利用贝叶斯推理&#xff0c;帮助读者掌握开…...

数据结构-3.1.栈的基本概念

一.栈的定义&#xff1a; 栈和线性表的区别&#xff1a;栈只能在表尾一端进行插入或者删除的操作&#xff0c;而线性表可以在任意一个地方进行插入或者删除 二.有关栈的关键术语&#xff1a; 三.栈的基本操作&#xff1a; 1.回顾线性表的基本操作&#xff1a; 2.栈的基本操作&…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

拟合问题处理

在机器学习中&#xff0c;核心任务通常围绕模型训练和性能提升展开&#xff0c;但你提到的 “优化训练数据解决过拟合” 和 “提升泛化性能解决欠拟合” 需要结合更准确的概念进行梳理。以下是对机器学习核心任务的系统复习和修正&#xff1a; 一、机器学习的核心任务框架 机…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...