【CT】LeetCode手撕—手撕快排
目录
- 题目
- 1-思路-快排
- 1-1 快排的核心思想
- 快速排序算法步骤
- 优美的调整区间
- 1-2 ⭐快排的实现
- 2- 实现
- ⭐912. 排序数组——题解思路
- 3- ACM 实现
题目
- 原题连接:912. 排序数组
1-思路-快排
1-1 快排的核心思想
- 选择一个基准
- 基准左侧的元素都小于该元素
- 基准右侧的元素都大于该元素
快速排序算法步骤
- ① 确定分界点:
- 方式有三种:第一种取左边界点 q[ l ];第二种取中间点q[ l+r ];第三种取右边界点q[ r ];随机
- ② 调整区间(★难点)
- 使得左半边区间内的数都小于等于 x ;右半边区间内的数都大于等于 x
- ③ 递归
- 递归处理左右两段
优美的调整区间
- 用两个指针分别指向数组的左边和右边,两个指针同时往中间走。
- 如果指针
i
指向的数组的元素值小于x
,则指针i
向右移动一位,以此类推一直往下移动,直到指针i
所指向的某个元素的值 大于等于x
,此时指针 i`` 停下不动。 - 同理此时移动指针
j
,若指针j
指向的元素的值大于等于x
则指针j
便向左移动,直到移动到j
所指向的值小于等于x
。
- 当两个指针都停下来的时候,swap 交换两个指针指向的数,之后两个指针继续往中间走,以此类推直到两个指针相遇为止。
1-2 ⭐快排的实现
public void quickSort(int[] nums,int left,int right){if(right<=left) return;// 定义 int i = left-1;int j = right+1;int x = nums[(i+j)/2];while(i<j){do{i++;}while(nums[i]<x);do{j--;}while(nums[j]>x);if(i<j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}quickSort(nums,left,j);quickSort(nums,j+1,right);}
2- 实现
⭐912. 排序数组——题解思路
class Solution {public int[] sortArray(int[] nums) {quickSort(nums,0,nums.length-1);return nums;}public void quickSort(int[] nums,int left,int right){if(right<=left) return;// 定义 int i = left-1;int j = right+1;int x = nums[(i+j)/2];while(i<j){do{i++;}while(nums[i]<x);do{j--;}while(nums[j]>x);if(i<j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}quickSort(nums,left,j);quickSort(nums,j+1,right);}
}
3- ACM 实现
public class quickSort {public static void quickSort(int[] nums,int left,int right){if(right<=left) return;// 定义int i = left-1;int j = right+1;int x = nums[(i+j)/2];while(i<j){do{i++;}while(nums[i]<x);do{j--;}while(nums[j]>x);if(i<j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}quickSort(nums,left,j);quickSort(nums,j+1,right);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组长度");int n = sc.nextInt();int[] nums = new int[n];for(int i = 0 ;i < n;i++){nums[i] = sc.nextInt();}quickSort(nums,0,nums.length-1);System.out.println("排序结果为");for (int i:nums){System.out.print(i+" ");}}
}
相关文章:
【CT】LeetCode手撕—手撕快排
目录 题目1-思路-快排1-1 快排的核心思想快速排序算法步骤优美的调整区间 1-2 ⭐快排的实现 2- 实现⭐912. 排序数组——题解思路 3- ACM 实现 题目 原题连接:912. 排序数组 1-思路-快排 1-1 快排的核心思想 选择一个基准 基准左侧的元素都小于该元素基准右侧的元…...
使用ARK工具ATool清除典型蠕虫MyDoom
1 概述 在长期的日常安全事件监测过程中,安天CERT经常捕获到大量的MyDoom蠕虫样本和传播该蠕虫的钓鱼邮件。受害主机感染MyDoom后会被放置后门,以便攻击者下发后续恶意软件,进行攻击或窃密等操作。MyDoom蠕虫最早发现于2004年&…...
在hue中使用ooize调度ssh任务无法执行成功,无法查看错误
ssh执行失败,但是hue没有给出明确的错误原因: 经过经验分析,原来是服务器上的sh文件用的是doc/window格式,需要使用notepad将格式改为unix之后就可以正常执行。 特此记录,避免遗忘知识点...
一套轻量、安全的问卷系统基座,提供面向个人和企业的一站式产品级解决方案
大家好,今天给大家分享的是一款轻量、安全的问卷系统基座。 XIAOJUSURVEY是一套轻量、安全的问卷系统基座,提供面向个人和企业的一站式产品级解决方案,快速满足各类线上调研场景。 内部系统已沉淀 40种题型,累积精选模板 100&a…...
3秒生成!这个AI模型画风也太治愈了,新手也能轻松驾驭
还在为不会画画而苦恼吗?别担心,今天给大家介绍一个超好用的AI模型——Soft and Squishy Linework,即使是小白也能轻松生成可爱的动漫图像! Soft and Squishy Linework:专门生成柔和的、低保真(lofi&#…...
数字人全拆解:如何构建一个基于大模型的实时对话3D数字人?
简单地说,数字人就是在数字世界的“人”。当前语境下我们谈到的数字人通常指的是借助AI技术驱动的虚拟世界人物,具备与真实人类相似甚至接近的外形、感知、交互与行为能力。 AI技术在智能数字人的应用中举足轻重,特别是随着大模型能力的涌现…...
实战 | 基于YOLOv10的车辆追踪与测速实战【附源码+步骤详解】
《博主简介》 小伙伴们好,我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍感谢小伙伴们点赞、关注! 《------往期经典推…...
2024北京智源大会
北京智源大会是年度国际性人工智能高端学术交流的盛会,定位于内行的AI盛会。智源大会紧密围绕当前人工智能学术领域迫切需要解决的问题,以及产业落地过程中存在的诸多挑战,开展深入探讨。智源研究院是2018年11月份成立的一家人工智能领域的新…...
youlai-boot项目的学习—本地数据库安装与配置
数据库脚本 在项目代码的路径下,有两个版本的mysql数据库脚本,使用对应的脚本就安装对应的数据库版本,本文件选择了5 数据库安装 这里在iterm2下使用homebrew安装mysql5 brew install mysql5.7注:记得配置端终下的科学上网&a…...
Android平台如何实现多路低延迟RTSP|RTMP播放?
技术背景 实际上,我们在2015年做Android平台RTSP、RTMP播放模块的时候,第一版就支持了多实例播放,因为SDK设计比较灵活,做个简单的player实例封装即可实现多实例播放(Android Unity的就有多路demo)&#x…...
深入探索Java开发世界:Java基础~类型分析大揭秘
文章目录 一、基本数据类型二、封装类型三、类型转换四、集合类型五、并发类型 Java基础知识,类型知识点梳理~ 一、基本数据类型 Java的基本数据类型是语言的基础,它们直接存储在栈内存中,具有固定的大小和不变的行为。 八种基本数据类型的具…...
短URL服务设计
引言 在营销系统里,为了增加系统的活跃用户数,经常会有各种各样的营销活动。这类活动几乎都是为了充分利用存量用户的价值,促使他们分享产品或App以达到触达到更多用户的目的。又或者是出于营销目的,群发优惠券触达短信这种场景。…...
Kafka集成flume
1.flume作为生产者集成Kafka kafka作为flume的sink,扮演消费者角色 1.1 flume配置文件 vim $kafka/jobs/flume-kafka.conf # agent a1.sources r1 a1.sinks k1 a1.channels c1 c2# Describe/configure the source a1.sources.r1.type TAILDIR #记录最后监控文件…...
如何让视频有高级感 高级感视频制作方法 高级感视频怎么剪 会声会影视频剪辑制作教程 会声会影中文免费下载
高质量视频通常具有清晰的画面、优质的音频和令人印象深刻的视觉效果。这篇文章来了解如何让视频有高级感,高级感视频制作方法。 一、如何让视频有高级感 要让视频有高级感,要注意以下几个要点: 1、剧本和故事性:一个好的剧本和…...
详解|访问学者申请被拒原因有哪些?
访问学者项目为全球科研人员提供了一个难得的机会,让他们能够跨越国界,深入不同的学术环境,进行学术交流和合作。然而,并非所有申请者都能如愿以偿地获得这一机会。本文将对访问学者申请中常见的被拒原因进行详细解析,…...
[鹤城杯 2021]BabyRSA
题目: from Crypto.Util.number import getPrime, bytes_to_long from secret import flagp getPrime(1024) q getPrime(1024) n p * q e 65537 hint1 p >> 724 hint2 q % (2 ** 265) ct pow(bytes_to_long(flag), e, n) print(hint1) print(hint2) p…...
西安市工业倍增引导基金子基金申报条件流程和材料程序指南(2024年)
一、基本情况 产业投资基金是以产业发展为首要目标,围绕经济社会发展规划和产业发展政策,发挥“有效市场”作用,支持重点领域、重点产业、重点区域(如:全市六大支柱产业、五大新兴产业领域成熟期重点规模以上企业以及“…...
微型丝杆的耐用性和延长使用寿命的关键因素!
无论是机械设备,还是精密传动元件,高精度微型丝杆是各种机械设备中不可或缺的重要组件。它的精度和耐用性直接影响着工作效率和产品品质,在工业技术不断进步的情况下,对微型丝杆的性能要求也越来越高,如何提升微型丝杆…...
音频文件下载后,如何轻松转换格式?
在我们日常的数字生活中,下载各种音频文件是司空见惯的事情。然而,有时候我们可能需要将这些音频文件转换为不同的格式,以适应不同的设备或编辑需求。无论您是希望将下载的音频文件转换为通用的MP3格式,还是需要将其转换为高保真的…...
Intel平台,13600KF+3060Ti,虚拟机安装macOS 14(2024年6月)
距离上次装macOS虚拟机已经有一段时间了,macOS系统现在大版本升级的速度也是越来越快了,由于Office只支持最新三个版本的macOS,所以现在保底也得安装macOS 12了,我这次是用macOS 14做实验,13和12的安装方式和macOS 14一…...
Cookie、Session、Token的关系和区别
关系 Session与Cookie:Session通常依赖于Cookie来工作。当服务器为客户端创建一个Session时,它会在服务器上存储与客户端相关的信息,并将一个唯一的SessionID通过Cookie发送给客户端。客户端在后续的请求中会携带这个Cookie(包含…...
Windows 11 中安装 Docker Desktop 并安装镜像
本该主要介绍在 Windows 11 中安装 Docker Desktop 时的一些准备工作,以及该如何下载和安装,然后分别使用管理界面和 Docker 命令安装两个镜像。 一、准备工作 在 Windows 11 中安装 Docker Desktop 前,需要做一些准备。打开 【Windows 功能…...
深入剖析Java线程池之“newWorkStealingPool“
1. 概述 newWorkStealingPool 是Java 8中引入的一个新型线程池,它基于ForkJoinPool实现,并采用了“工作窃取”(Work-Stealing)算法。这种线程池特别适用于可并行化且计算密集型的任务,能够充分利用多核CPU资源,提高任务执行效率。 2. 工作窃取算法(Work-Stealing Algor…...
《跟我一起学“网络安全”》——安全设备
安全设备 一、安全设备–IDS IDS入侵检测 (1)什么是入侵检测: 入侵检测系统(intrusion detection system,简称“IDS”)是一种对网络传输进行即时监视,在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。…...
猜测Tomcat如何实现WebSocket协议
一、WebSocket协议的实现 (一)WebSocket是官方的协议接口标准。 (二)如果一门编程语言可以网络连接和并发,就能创建一种WebSocket实现。 (三)同一种编程语言,有不同的协议实现版本和框架。 二、Tomcat实现 在Tomcat容器中实现了对应的WebSocket版本&am…...
uniApp @input事件更改输入框值,值改变了但是页面没更新新的值
<uni-easyinputtype"text"trim"all":inputBorder"false"v-model"customFormData.completePercent"input"(val) > completeOnInput(val)"placeholder"请输入" /> function completeOnInput(val) {let num…...
两行css 实现瀑布流
html <ul ><li><a href"" ><img src"05094532gc6w.jpg" alt"111" /><p>传奇</p></a></li><li><a href"" ><img src"05094532gc6w.jpg" alt"111"…...
Centos7.9部署单节点K8S环境
Centos7.9部署单节点K8S环境 通过Centos extras镜像源安装K8S环境,优点是方便快捷,缺点是版本较低,安装后的版本为1.5.2。 1. 准备工作 关闭selinux [rootlocalhost ~]# cat /etc/selinux/config# This file controls the state of SELin…...
【CV】stable diffusion初步理解
来自gpt-4o Stable diffusion 和DALLE的关系 Stable Diffusion 和 DALL-E 都是生成图像的人工智能模型,但它们有不同的开发背景和技术实现。 Stable Diffusion: 开发者: 由Stability AI开发,并与CompVis和LAION等组织合作。技术: 基于扩散模型…...
足底筋膜炎最好的恢复办法
足底筋膜炎是一种由足底筋膜受到炎症刺激而引起的疼痛和不适的疾病。其典型症状主要包括: 1、足底疼痛:这是足底筋膜炎最常见的症状。疼痛通常位于足跟部位,患者可能感到刺痛或灼热感。尤其在早晨起床或长时间站立后,这种疼痛感会…...
上海企业网站设计制作/销售网站排名
hash赋能前言一、缺失的第一个正数二、hash赋能1、hashSet2、原地数组hash总结参考文献前言 hash赋能可以为后面的工作大大减少搜索的时间,可用hash数组、hashSet、hashMap、原地数组hash。 一、缺失的第一个正数 二、hash赋能 1、hashSet //hash赋能//Time:O(n…...
wordpress 段落显示不全/长春seo外包
[十二省联考2019]异或粽子 先吐槽一下,在考场上完全没有将这道题和超级钢琴联系起来,然后\(GG\),喜提\(60\)走人 赛后听说直接上可持久化\(Trie\)用堆维护就好了 然后自己回来又打开了超级钢琴. 这道题就有思路了 很明显,这道题我们可以利用前缀和优化到最大的\(k\)对数的异或和…...
成都 视频网站建设/seo快速提升排名
前几天做了一个代码框的管理系统,我这几天抽空把他做成了图形化界面的样子,利用的是Tkinter。准备工作就是建立数据库可以参考之前的博客:python mysql学生成绩管理系统 1 首先我写了一个登陆界面类 login: 这个界面就是实现用户…...
做网站怎么买断源码/如何快速推广
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼看下 GtkEntry 的源码不就知道了。。。gtk_entry_get_display_text...if (end_pos < start_pos)return g_strdup ("");else if (priv->visible){start g_utf8_offset_to_pointer (text, start_pos);end g_utf8_o…...
二手网站专业做附近人的有吗/杭州优化排名哪家好
今天从跟公司牛人那学到的~避免以后忘了赶快记录下来 平时JS的function的返回值可以是一个数值,也可以是一个对象({name:abc,age:123}),更可以是一个函数(这里我是第一次听说),从网上搜了搜&…...
广州高端网站设计/品牌搜索引擎服务优化
查看报错日志路径:/usr/local/mysql/data/*.err 按照提示修改vi /etc/my.cnf配置文件的lower_case_table_names 0 保存后,重启mysql就可以:service mysql start...