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

【912.排序数组】

目录

  • 一、题目描述
  • 二、算法原理
    • 2.1快速排序
    • 2.2归并排序
  • 三、代码实现
  • 3.1快排代码实现
  • 3.2归并代码实现

一、题目描述

在这里插入图片描述

二、算法原理

2.1快速排序

在这里插入图片描述

2.2归并排序

在这里插入图片描述

三、代码实现

3.1快排代码实现

class Solution {
public:int getRandom(int left,int right,vector<int>& nums){return nums[rand()%(right-left+1)+left];}void _sortArray(int left,int right,vector<int>& nums){if(left>right){return ;}int key=getRandom(left,right,nums);int l=left-1,r=right+1,i=left;while(i<r){if(nums[i]<key)swap(nums[++l],nums[i++]);else if(nums[i]>key)swap(nums[i],nums[--r]);elsei++;}_sortArray(left,l,nums);_sortArray(r,right,nums);}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));_sortArray(0,nums.size()-1,nums);return nums;}
};

3.2归并代码实现

class Solution {
public:void mergeSort(vector<int>& nums,int left,int right){if(left>=right){return;}int mid=left+(right-left)/2;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//合并两个有序数组vector<int> v(right-left+1);int cur1=left,cur2=mid+1,i=0;while((cur1<=mid)&&(cur2<=right)){if(nums[cur1]<nums[cur2]){v[i++]=nums[cur1++];}else{v[i++]=nums[cur2++];}}while(cur1<=mid) v[i++]=nums[cur1++];while(cur2<=right) v[i++]=nums[cur2++];//还原数组for(int i=left;i<=right;i++){nums[i]=v[i-left];}}vector<int> sortArray(vector<int>& nums) {mergeSort(nums,0,nums.size()-1);return nums;}
};

相关文章:

【912.排序数组】

目录 一、题目描述二、算法原理2.1快速排序2.2归并排序 三、代码实现3.1快排代码实现3.2归并代码实现 一、题目描述 二、算法原理 2.1快速排序 2.2归并排序 三、代码实现 3.1快排代码实现 class Solution { public:int getRandom(int left,int right,vector<int>&…...

【动态规划】583. 两个字符串的删除操作、72. 编辑距离

提示&#xff1a;努力生活&#xff0c;开心、快乐的一天 文章目录 583. 两个字符串的删除操作&#x1f4a1;解题思路&#x1f914;遇到的问题&#x1f4bb;代码实现&#x1f3af;题目总结 72. 编辑距离&#x1f4a1;解题思路&#x1f914;遇到的问题&#x1f4bb;代码实现&…...

Gradient conjugate priors and multi-layer neural networks

动机 先验参数 m , α , β , v m,\alpha,\beta,v m,α,β,v和随机变量 τ \tau τ KL散度的形式是&#xff1a; Dynamics of m , α , β , v m,\alpha,\beta,v m,α,β,v Dynamics of m , β , v m,\beta,v m,β,v for a fixed α \alpha α 绿色轨迹连接初始点和目标点…...

DistributedDataParallel数据不均衡

背景 在使用 DistributedDataParallel 进行数据并行训练时&#xff0c;每次反向传播都需要执行 all_reduce 操作以同步各个进程的梯度。all_reduce 需要进程组中的所有进程参与&#xff0c;如果某一个进程没有执行 all_reduce&#xff08;一个进程的输入较其他进程少&#xff…...

Cloud Studio连接MySQL,Access denied for一系列问题

官方文档有写如何安装Mysql $ apt update $ apt install mysql-server mysql-client -y$ service mysql start mysql -uroot -p123456进入MySQL命令行 问题出在连接数据库这一步&#xff0c;命令行能进去&#xff0c;但是数据库插件和代码都连不上 Access denied for 大概率…...

经典题型---旋转数组

经典题型—旋转数组 文章目录 经典题型---旋转数组一、题目二、代码实现 一、题目 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步…...

vue如何实现登录数据的持久化

Vue.js是一款流行的JavaScript框架&#xff0c;它可以帮助开发者构建高效且易于维护的单页面应用程序。在Vue.js中&#xff0c;实现登录数据的持久化是一个重要的任务&#xff0c;因为它可以帮助用户保持登录状态并避免频繁的登录操作。在本文中&#xff0c;我们将讨论Vue.js如…...

【Unity3D编辑器开发】Unity3D中实现Transform组件拓展,快速复制、粘贴、复原【非常实用】

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 在开发中&#xff0c;常常会遇到频繁复制粘贴物体的坐标、旋转…...

求解仿射变换矩阵

仿射变换是图形学中经常用到的方法&#xff0c;通常但是仿射变换的系数是未知的&#xff0c;需要找到变换前后的三对对应点进行求解。 from affine import Affine import numpy as np参考文献 矩阵最小二乘法求解仿射变换矩阵 def solve_affine(init_points, goal_points) -&…...

【每日一题】—— 最大素因子

&#x1f30f;博客主页&#xff1a;PH_modest的博客主页 &#x1f6a9;当前专栏&#xff1a;每日一题 &#x1f48c;其他专栏&#xff1a; &#x1f534; 每日反刍 &#x1f7e1; C跬步积累 &#x1f7e2; C语言跬步积累 &#x1f308;座右铭&#xff1a;广积粮&#xff0c;缓称…...

【JavaEE】JUC 常见的类 -- 多线程篇(8)

JUC 常见的类 1. Callable 接口2. ReentrantLock3. 原子类4. 线程池5. 信号量 Semaphore6. CountDownLatch 1. Callable 接口 Callable Interface 也是一种创建线程的方式 Runnable 能表示一个任务 (run方法) – 返回 voidCallable 也能表示一个任务(call方法) 返回一个具体的…...

java项目运行时信息获取

大体思路如下&#xff0c;想要获取启动时处理器数量、jvm 相关信息&#xff0c;操作系统信息、运行机器信息 运行机器信息 import org.slf4j.Logger; import org.slf4j.LoggerFactory;import java.lang.invoke.MethodHandles;/*** 机器工具类*/ public abstract class ServerU…...

【LeetCode】71. 简化路径

1 问题 给你一个字符串 path &#xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 &#xff08;以 / 开头&#xff09;&#xff0c;请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中&#xff0c;一个点&#xff08;.&#xff09;表示当前目录本身&#xf…...

操作系统【OS】进程的控制【进程的创建、终止、阻塞、唤醒】

定义和过程 对应事件 创建 允许一个进程创建另一个进程允许子进程继承父进程所拥有的资源创建进程的过程如下&#xff1a; 申请一个空白的 PCB&#xff0c;并向 PCB 中填写一些控制和管理进程的信息&#xff0c;比如进程的唯一标识等&#xff1b;为该进程分配运行时所必需的…...

写一个简单的解释器(2) 构建标记流

确定标记类型 分为几个大类&#xff1a; 用户符号&#xff08;类型/标识符/数字/字符串…)关键字 (流程控制和定义符)括号 &#xff08;这里暂时认为 [] 属于括号&#xff09;分号 上述四类标记基本囊括了 vc \texttt{vc} vc 中的所有最小单元的类型&#xff0c;但是因为构…...

Leetcode1833. 雪糕的最大数量

Every day a Leetcode 题目来源&#xff1a;1833. 雪糕的最大数量 解法1&#xff1a;贪心 排序 本题唯一的难点在于计数排序。 计数排序详解&#xff1a;C算法之计数排序 为了尽可能多的买到雪糕&#xff0c;我们选择从价格低的雪糕开始买&#xff0c;统计能够买到的雪糕…...

idea 里 没有svn选项的处理办法

总结一下没有svn选项的几种情况&#xff1a; 情况1&#xff1a;IntelliJ IDEA打开带SVN信息的项目不显示SVN信息&#xff0c;项目右键SVN以及图标还有Changes都不显示解决方法 在VCS菜单中有个开关&#xff0c;叫Enabled Version Control Integration&#xff0c;在打开的窗口…...

基于SpringBoot的招生管理系统

基于SpringBoot的招生管理系统的设计与实现~ 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatisVue工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 主页 登录界面 管理员界面 用户界面 摘要 基于SpringBoot的招生管理系统是一款现…...

01、MySQL-------性能优化

目录 一、影响性能的相关因素存储过程&#xff1a; 二、sql优化1>、Mysql系统架构2>、引擎区别&#xff1a; 3>、索引1、什么是索引&#xff1f;联合主键索引理解&#xff1a;索引长度理解&#xff1a;什么是慢查询&#xff1f; 1&#xff09;、索引理解2&#xff09;…...

Flutter - APP跳转高德、百度、腾讯、谷歌地图

demo 地址: https://github.com/iotjin/jh_flutter_demo 代码不定时更新&#xff0c;请前往github查看最新代码 这里介绍的是不需要自己开发地图&#xff0c;直接通过给定的经纬度&#xff0c;跳转到三方地图APP调用导航的方式 一种是写的工具类&#xff0c;一种是通过调用三方…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...