【练习】分治--快排思想

  • 🎥 个人主页:Dikz12
  • 🔥个人专栏:算法(Java)
  • 📕格言:吾愚多不敏,而愿加学
  • 欢迎大家👍点赞✍评论⭐收藏

目录

颜色分类

题目描述 

题解  

代码实现

排序数组

题目描述 

 题解

代码实现 

数组中的第k个最大元素

题目描述 

 题解

​编辑 代码实现

库存管理III( 最小k个数)

题目描述 

​编辑 题解

代码实现 


                                                   分治:分而治之. 

颜色分类

题目描述 

题解  

 解法:三指针(数组分三块).

 

代码实现

    public void sortColors(int[] nums) {int i = 0, left = -1, right = nums.length;while(i < right) {if (nums[i] == 0) {swap(nums,++left,i++);} else if (nums[i] == 1) {i++;}else {swap(nums,--right,i);}} }public void swap(int[] nums, int i , int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

排序数组

题目描述 

 题解

 解法:快速排序(数组分三块+随机选择基准).

快排最核⼼的⼀步就是 Partition (分割数 据):将数据按照⼀个标准,分成左右两部分。
这里 不是使用的是将数组分成两部分(挖坑法、Hoare法)。

而是使⽤荷兰国旗问题的思想,将数组划分为 左 中 右 三部分:左边是⽐基准元素⼩的数据, 中间是与基准元素相同的数据,右边是⽐基准元素⼤的数据。然后再去递归的排序左边部分和右边 部分即可(可以舍去⼤量的中间部分)。
在处理数据量有很多重复的情况下,效率会⼤⼤提升!!!

数组分三块,过程就跟上题一样就不在进行详述.

优化方式有:随机选择基准 和 三位取中.

 

代码实现 

    public int[] sortArray(int[] nums) {qsort(nums,0,nums.length - 1);return nums;}public void qsort(int[] nums,int l , int r) {//递归结束if (l >= r) {return;}//数组分三块int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, i = l, right = r + 1;while(i < right) {if(nums[i] < key) {swap(nums,++left,i++);}else if (nums[i] == key) {i++;} else {swap(nums,--right,i);}}//[0,left]  [left+1,right-1]  [right,r]qsort(nums,l,left);qsort(nums,right,r);}public void swap(int[] nums,int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

 挖坑法、Hoare法+优化:

 数组分三块+优化

数组中的第k个最大元素

题目描述 

 

 题解

解法:快速选择算法(数组分三块+随机选取基准元素) 。

在快排中,当我们把数组「分成三块」之后: [l, left] [left + 1, right - 1]
[right, r] ,我们可以通过计算每⼀个区间内元素的「个数」,进⽽推断出我们要找的元素是
在「哪⼀个区间」⾥⾯。 那么我们可以直接去「相应的区间」去寻找最终结果就好了。

 代码实现

    public int findKthLargest(int[] nums, int k) {return qsort(nums,0,nums.length-1,k);}public int qsort(int[] nums,int l ,int r, int k) {//结束条件if (l >= r) {return nums[l];}//1.随机选取基准int key = nums[new Random().nextInt(r - l + 1) + l];//2.数组分"三块"int i = l , left = l - 1, right = r + 1;while(i < right) {if(nums[i] < key) {swap(nums,++left,i++);} else if (nums[i] == key) {i++;} else{swap(nums,--right,i);}}// 3.区间个数 [l,left]  [left + 1, right - 1]  [right,r]int b = right - left - 1, c = r - right + 1;if(c >= k) {return qsort(nums,right,r,k);} else if (b + c >= k) {return key;} else {return qsort(nums,l,left,k - c - b);}}public void swap(int[] nums, int i , int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

库存管理III( 最小k个数)

题目描述 

 题解

解法一:堆排.(大根堆)O(NlogN).

解法二:快速选择算法(数组分三块+随机选取基准元素) O(N) 

在快排中,当我们把数组「分成三块」之后: [l, left] [left + 1, right - 1]
[right, r] ,我们可以通过计算每⼀个区间内元素的「个数」,进⽽推断出最⼩的 k 个数在哪
些区间⾥⾯。 那么我们可以直接去「相应的区间」继续划分数组即可。

 

代码实现 

    public int[] inventoryManagement(int[] nums, int cnt) {qsort(nums,0,nums.length-1,cnt);int[] ret = new int[cnt];for(int i = 0; i < cnt; i++) {ret[i] = nums[i];}return ret;}public void qsort(int[] nums, int l, int r, int k) {if(l >= r) {return;}//1.随机选取基准int key = nums[new Random().nextInt(r - l + 1) + l];//2.数组分三块int i = l, left = l - 1,right = r + 1;while(i < right) {if(nums[i] < key) {swap(nums,++left,i++);} else if (nums[i] == key) {i++;} else {swap(nums,--right,i);}}//3. [l,left]  [left+1,right-1]  [right,r]int a = left - l + 1, b = right - left - 1;if (a >= k) {qsort(nums,l,left,k);} else if(a + b >= k) {return;} else {qsort(nums,right,r,k - a - b);}}public void swap(int[] nums, int i , int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1424243.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

华为正式放弃高通芯片 | 百能云芯

5月15日&#xff0c;据外媒最新报道&#xff0c;高通公司正式确认&#xff0c;华为已无需依赖其处理器供应。 在出口许可被正式吊销前&#xff0c;高通的首席财务官已公开表示&#xff0c;预计明年与华为之间的芯片销售将为零&#xff0c;因为华为决定不再从高通购买4G芯片。 报…

策略模式详解

策略模式 1 概述 先看下面的图片&#xff0c;我们去旅游选择出行模式有很多种&#xff0c;可以骑自行车、可以坐汽车、可以坐火车、可以坐飞机。 作为一个程序猿&#xff0c;开发需要选择一款开发工具&#xff0c;当然可以进行代码开发的工具有很多&#xff0c;可以选择Idea进…

信创改造2---java集成TongLink/Q

上一篇针对TongLINK/Q的安装部署 http://t.csdnimg.cn/9ss7l ,这篇具体说明java集成 1. 准备工作 根据实际修改连接URL等信息 vim TLQ8/etc/tlqjndi.conf 2. JAVA集成 将TongJMS.jar加载到自己的项目中 发送消息 package com.keyou.proj.authentication.service.utils;…

C++11 新特性 常量表达式 constexpr

为了解决常量无法确定的问题&#xff0c;C11在新标准中提出了关键字constexpr&#xff0c;它能够有效地定义常量表达式&#xff0c;并且达到类型安全、可移植、方便库和嵌入式系统开发的目的。 一、常量的不确定性 在C11标准以前&#xff0c;我们没有一种方法能够有效地要求一…

ModuleNotFoundError: No module named ‘openpyxl‘的解决方案

问题描述&#xff1a; ModuleNotFoundError: No module named ‘openpyxl’ 这个错误表示你的 Python 环境中没有安装 openpyxl 这个模块。openpyxl 是一个用于读写 Excel 2010 xlsx/xlsm/xltx/xltm 文件的 Python 库。 解决方案&#xff1a; 要解决这个问题&#xff0c;你需…

Java后端面试常见问题

Java后端面试 经历了两个月的面试和准备&#xff0c;下面对常见的八股文进行总结。有些问题是网上看到的面经里提到的&#xff0c;有些是我真实面试过程遇到的。 异常 1、异常分为哪几种&#xff1f;他们的父类是什么&#xff1f; 注意&#xff1a;所有异常对象的父类为Thr…

做简单易用的GIS资源管理软件

在室外资源管理领域&#xff0c;采用基于GIS的解决方案已成为主流趋势&#xff0c;旨在实现资源的高效利用和管理。GIS技术结合资源对象的规划、定位和监控&#xff0c;为企业提供全面的管理方案&#xff0c;从而优化资源使用、提高运营效率和降低成本。 然而&#xff0c;许多资…

OpenAI新模型GPT-4o“炸裂登场” 响应速度堪比真人 关键还免费!

GPT-4o模型基于来自互联网的大量数据进行训练&#xff0c;更擅长处理文本和音频&#xff0c;并且支持50种语言。更值得一提的是&#xff0c;GPT-4o最快可以在232毫秒的时间内响应音频输入&#xff0c;几乎达到了人类的响应水平。 GPT-4o有多“炸裂”&#xff1f;核心能力有三 G…

网工内推 | 测试工程师,NA认证以上,15薪,补充医疗险

01 天视通 招聘岗位&#xff1a;测试工程师 职责描述&#xff1a;1、网络视频监控相关软件产品测试&#xff0c;及行测试记录和相应各种文档资料/手册编写&#xff1b;2、负责编写测试计划、测试用例、搭建测试环境、执行测试&#xff1b;3、进行BUG验证根据测试结果&#xff…

光伏行业该如何起步?

随着全球对可再生能源的需求日益增长&#xff0c;光伏行业作为其中的佼佼者&#xff0c;正迎来前所未有的发展机遇。然而&#xff0c;对于新进入者或希望在这一领域有所建树的企业来说&#xff0c;如何起步并稳健发展是一个值得深思的问题。以下是一些关于光伏行业起步的建议。…

新手也能看懂的前端单元测试框架:Vitest

单元测试的概念及作用 1.什么是单元测试&#xff1f; 单元测试是测试中的一个重要环节&#xff0c;它针对软件中的最小可测试单元进行验证&#xff0c;通常是指对代码中的单个函数、方法或模块进行测试。 单元测试旨在确定特定部分代码的行为是否符合预期&#xff0c;通过针…

中青杯全国大学生数学建模竞赛纳入多所高校学科竞赛认定目录

2024年第六届中青杯全国大学生数学建模竞赛将于2024年5月23日17:00至5月26日17:00举行,中青杯全国大学生数学建模竞赛是中国高校学科竞赛中规模较大、影响较广的学科竞赛之一,并且纳入多所高校学科竞赛认定目录。 报名截止时间:2024年5月23日12:00 报名网站:http://www.c…

FPGA - GTX收发器-K码 以及 IBERT IP核使用

一&#xff0c;前言 在FPGA - Xilinx系列高速收发器---GTX中详细介绍了GTX的基础知识&#xff0c;以及IP核的调用&#xff0c;下面将补充一下GTX在使用中的高速串行数据流在接收和发送时的控制与对齐&#xff08;K码&#xff09;&#xff0c;以及高速接口GTX&#xff0c;如果G…

深度解析 Spring 源码:解密AOP切点和通知的实现机制

文章目录 深度解析 Spring 源码&#xff1a;解密AOP切点和通知的实现机制一、Spring AOP的基础知识1.1 AOP的核心概念&#xff1a;切点、通知、切面等1.2 Spring AOP与传统AOP的区别和优势 二、深入分析切点和通知的实现2.1 研究 Pointcut 接口及其实现类2.1.1 Pointcut 接口2.…

Towards Novel Class Discovery: A Study in Novel Skin Lesions Clustering

文章目录 Towards Novel Class Discovery: A Study in Novel Skin Lesions Clustering摘要方法实验结果 Towards Novel Class Discovery: A Study in Novel Skin Lesions Clustering 摘要 在识别皮肤疾病的皮肤镜图像方面&#xff0c;现有的深度学习模型表现出了令人期待的性…

石碑之谜:滚动机关

描述 在蒙德和璃月的边界地带&#xff0c;有一个被遗忘的神庙&#xff0c;里面有一个奇怪的机关&#xff1a;滚动石碑。小熊必须操作这个112的长方体石碑&#xff0c;使其通过不同的地面环境&#xff0c;最终放置到神秘的符号“O”上&#xff0c;以解开通往宝藏的大门。 石碑…

Excel提取某一列的唯一值

点击【筛选】&#xff08;【高级筛选】&#xff09;&#xff0c;参数里&#xff1a; 列表区域&#xff1a;为需要选择唯一值的那一列复制到&#xff1a;生成唯一值的目标区域 据说新版本的excel有了unique()函数&#xff0c;可以很快捷的选择某一列的唯一值&#xff0c;但是博…

重磅!OpenAI发布GPT-4o,非常惊艳语音版ChatGPT!

5月15日凌晨&#xff0c;谷歌召开“ I/O 2024”&#xff0c;生成式AI成为本次大会的重点并发布了一系列产品和多款大模型。 其中&#xff0c;谷歌DeepMind发布了一款全新的AI 代理&#xff08;Agent&#xff09;产品Project Astra&#xff0c;可以像昨天OpenAI发布的GPT4o一样…

正点原子[第二期]Linux之ARM(MX6U)裸机篇学习笔记-15.6讲 GPIO中断实验-GPIO驱动添加中断处理函数

前言&#xff1a; 本文是根据哔哩哔哩网站上“正点原子[第二期]Linux之ARM&#xff08;MX6U&#xff09;裸机篇”视频的学习笔记&#xff0c;在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。…

新书速览|Django 5 Web应用开发实战

构建未来&#xff0c;用Django 5打造全新Web应用 本书内容 《Django 5 Web应用开发实战》集Django架站基础、项目实践、开发经验于一体&#xff0c;是一本从零基础到精通Django Web企业级开发技术的实战指南。《Django 5 Web应用开发实战》内容以Python 3.x和Django 5版本为基础…