当前位置: 首页 > 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一…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...