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

【CT】LeetCode手撕—手撕快排

目录

  • 题目
  • 1-思路-快排
    • 1-1 快排的核心思想
      • 快速排序算法步骤
      • 优美的调整区间
    • 1-2 ⭐快排的实现
  • 2- 实现
    • ⭐912. 排序数组——题解思路
  • 3- ACM 实现

题目

  • 原题连接:912. 排序数组

1-思路-快排

1-1 快排的核心思想

  • 选择一个基准
    • 基准左侧的元素都小于该元素
    • 基准右侧的元素都大于该元素

image.png

快速排序算法步骤

  • ① 确定分界点:
    • 方式有三种:第一种取左边界点 q[ l ];第二种取中间点q[ l+r ];第三种取右边界点q[ r ];随机
  • ② 调整区间(★难点)
    • 使得左半边区间内的数都小于等于 x ;右半边区间内的数都大于等于 x
  • ③ 递归
    • 递归处理左右两段

优美的调整区间

  • 用两个指针分别指向数组的左边和右边,两个指针同时往中间走。
  • 如果指针 i 指向的数组的元素值小于 x ,则指针 i 向右移动一位,以此类推一直往下移动,直到指针 i 所指向的某个元素的值 大于等于 x,此时指针 i`` 停下不动。
  • 同理此时移动指针 j ,若指针 j 指向的元素的值大于等于 x 则指针 j 便向左移动,直到移动到 j 所指向的值小于等于 x

766AC1FD4EB24C2579F850B29BD8E35B.png

  • 当两个指针都停下来的时候,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 实现 题目 原题连接&#xff1a;912. 排序数组 1-思路-快排 1-1 快排的核心思想 选择一个基准 基准左侧的元素都小于该元素基准右侧的元…...

使用ARK工具ATool清除典型蠕虫MyDoom

1 概述 在长期的日常安全事件监测过程中&#xff0c;安天CERT经常捕获到大量的MyDoom蠕虫样本和传播该蠕虫的钓鱼邮件。受害主机感染MyDoom后会被放置后门&#xff0c;以便攻击者下发后续恶意软件&#xff0c;进行攻击或窃密等操作。MyDoom蠕虫最早发现于2004年&…...

在hue中使用ooize调度ssh任务无法执行成功,无法查看错误

ssh执行失败&#xff0c;但是hue没有给出明确的错误原因&#xff1a; 经过经验分析&#xff0c;原来是服务器上的sh文件用的是doc/window格式&#xff0c;需要使用notepad将格式改为unix之后就可以正常执行。 特此记录&#xff0c;避免遗忘知识点...

一套轻量、安全的问卷系统基座,提供面向个人和企业的一站式产品级解决方案

大家好&#xff0c;今天给大家分享的是一款轻量、安全的问卷系统基座。 XIAOJUSURVEY是一套轻量、安全的问卷系统基座&#xff0c;提供面向个人和企业的一站式产品级解决方案&#xff0c;快速满足各类线上调研场景。 内部系统已沉淀 40种题型&#xff0c;累积精选模板 100&a…...

3秒生成!这个AI模型画风也太治愈了,新手也能轻松驾驭

还在为不会画画而苦恼吗&#xff1f;别担心&#xff0c;今天给大家介绍一个超好用的AI模型——Soft and Squishy Linework&#xff0c;即使是小白也能轻松生成可爱的动漫图像&#xff01; Soft and Squishy Linework&#xff1a;专门生成柔和的、低保真&#xff08;lofi&#…...

数字人全拆解:如何构建一个基于大模型的实时对话3D数字人?

简单地说&#xff0c;数字人就是在数字世界的“人”。当前语境下我们谈到的数字人通常指的是借助AI技术驱动的虚拟世界人物&#xff0c;具备与真实人类相似甚至接近的外形、感知、交互与行为能力。 AI技术在智能数字人的应用中举足轻重&#xff0c;特别是随着大模型能力的涌现…...

实战 | 基于YOLOv10的车辆追踪与测速实战【附源码+步骤详解】

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…...

2024北京智源大会

北京智源大会是年度国际性人工智能高端学术交流的盛会&#xff0c;定位于内行的AI盛会。智源大会紧密围绕当前人工智能学术领域迫切需要解决的问题&#xff0c;以及产业落地过程中存在的诸多挑战&#xff0c;开展深入探讨。智源研究院是2018年11月份成立的一家人工智能领域的新…...

youlai-boot项目的学习—本地数据库安装与配置

数据库脚本 在项目代码的路径下&#xff0c;有两个版本的mysql数据库脚本&#xff0c;使用对应的脚本就安装对应的数据库版本&#xff0c;本文件选择了5 数据库安装 这里在iterm2下使用homebrew安装mysql5 brew install mysql5.7注&#xff1a;记得配置端终下的科学上网&a…...

Android平台如何实现多路低延迟RTSP|RTMP播放?

技术背景 实际上&#xff0c;我们在2015年做Android平台RTSP、RTMP播放模块的时候&#xff0c;第一版就支持了多实例播放&#xff0c;因为SDK设计比较灵活&#xff0c;做个简单的player实例封装即可实现多实例播放&#xff08;Android Unity的就有多路demo&#xff09;&#x…...

深入探索Java开发世界:Java基础~类型分析大揭秘

文章目录 一、基本数据类型二、封装类型三、类型转换四、集合类型五、并发类型 Java基础知识&#xff0c;类型知识点梳理~ 一、基本数据类型 Java的基本数据类型是语言的基础&#xff0c;它们直接存储在栈内存中&#xff0c;具有固定的大小和不变的行为。 八种基本数据类型的具…...

短URL服务设计

引言 在营销系统里&#xff0c;为了增加系统的活跃用户数&#xff0c;经常会有各种各样的营销活动。这类活动几乎都是为了充分利用存量用户的价值&#xff0c;促使他们分享产品或App以达到触达到更多用户的目的。又或者是出于营销目的&#xff0c;群发优惠券触达短信这种场景。…...

Kafka集成flume

1.flume作为生产者集成Kafka kafka作为flume的sink&#xff0c;扮演消费者角色 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 #记录最后监控文件…...

如何让视频有高级感 高级感视频制作方法 高级感视频怎么剪 会声会影视频剪辑制作教程 会声会影中文免费下载

高质量视频通常具有清晰的画面、优质的音频和令人印象深刻的视觉效果。这篇文章来了解如何让视频有高级感&#xff0c;高级感视频制作方法。 一、如何让视频有高级感 要让视频有高级感&#xff0c;要注意以下几个要点&#xff1a; 1、剧本和故事性&#xff1a;一个好的剧本和…...

详解|访问学者申请被拒原因有哪些?

访问学者项目为全球科研人员提供了一个难得的机会&#xff0c;让他们能够跨越国界&#xff0c;深入不同的学术环境&#xff0c;进行学术交流和合作。然而&#xff0c;并非所有申请者都能如愿以偿地获得这一机会。本文将对访问学者申请中常见的被拒原因进行详细解析&#xff0c;…...

[鹤城杯 2021]BabyRSA

题目&#xff1a; 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年)

一、基本情况 产业投资基金是以产业发展为首要目标&#xff0c;围绕经济社会发展规划和产业发展政策&#xff0c;发挥“有效市场”作用&#xff0c;支持重点领域、重点产业、重点区域&#xff08;如&#xff1a;全市六大支柱产业、五大新兴产业领域成熟期重点规模以上企业以及“…...

微型丝杆的耐用性和延长使用寿命的关键因素!

无论是机械设备&#xff0c;还是精密传动元件&#xff0c;高精度微型丝杆是各种机械设备中不可或缺的重要组件。它的精度和耐用性直接影响着工作效率和产品品质&#xff0c;在工业技术不断进步的情况下&#xff0c;对微型丝杆的性能要求也越来越高&#xff0c;如何提升微型丝杆…...

音频文件下载后,如何轻松转换格式?

在我们日常的数字生活中&#xff0c;下载各种音频文件是司空见惯的事情。然而&#xff0c;有时候我们可能需要将这些音频文件转换为不同的格式&#xff0c;以适应不同的设备或编辑需求。无论您是希望将下载的音频文件转换为通用的MP3格式&#xff0c;还是需要将其转换为高保真的…...

Intel平台,13600KF+3060Ti,虚拟机安装macOS 14(2024年6月)

距离上次装macOS虚拟机已经有一段时间了&#xff0c;macOS系统现在大版本升级的速度也是越来越快了&#xff0c;由于Office只支持最新三个版本的macOS&#xff0c;所以现在保底也得安装macOS 12了&#xff0c;我这次是用macOS 14做实验&#xff0c;13和12的安装方式和macOS 14一…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...