分治算法——912. 排序数组

在这里插入图片描述

文章目录

    • 🍈1. 题目
    • 🍌2. 算法原理
    • 🍏3. 代码实现

🍈1. 题目

题目链接:912. 排序数组 - 力扣(LeetCode)

给你一个整数数组 nums,请你将该数组升序排列。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

🍌2. 算法原理

如果不讲武德,直接sort排序,然后返回,这样也是能通过的,但是意义不大

image-20231201225154753

我们当然是选择用分治的思想,自己来实现这个快排。

这里简单讲解一下快排(以升序为例):

给一个数组,选定一个基准元素key,然后根据这个基准元素,将这个数组分为两部分:

  • key左边这个区间的元素全都是小于等于>= key
  • key右边的区间的元素全都是< key

接下来再将从左边的区域选取基准值、右边的区域选取基准值,依此重复这个操作

image-20231201230023386

这就是快排的核心思想。

不过这个的缺陷就是对应有着大量重复元素时,时间复杂度会退化到O(N2)

所以此题采用的是三路划分的思想,来实现快排

建议先看看此篇文章——分治算法——75. 颜色分类,思想一样

我们将数组分为三个区域,即:

  1. 小于key< key
  2. 等于key== key
  3. 大于key> key

和上面这个75.颜色分类题目同理,三个指针:leftrighti,这里分类套路三种情况

  1. nums[i] < keyswap(nums[++left] , nums[i++])
  2. nums[i] == keyi++
  3. nums[i] > keyswap(nums[--right] , nums[i])

为什么三路划分效率会高一点:

如果这个数组里面全都是key的时候,我们经过一次数组划分,中间这些元素全都是等于key的,接下来中间区域的元素不用管,去左右区间,但此时左右区间并不存在,直接退出递归,所以此时的复杂度从O(N2)降到了O(N)

优化——如何选取key值:

如果要将快排的时间复杂度将近为Nlog(N),要采用随机选key(大佬证明过),有兴趣的可以查阅《算法导论》这本书。

GPT回答(稍微看一下):
快速排序的时间复杂度分析涉及到分割的效率和基准值选择对数组分割的影响。
分割的效率:快速排序的性能高度依赖于数组分割的均匀性。理想情况下,每次分割都能将数组几乎均匀地划分成两个子数组。随机选择基准值可以增加分割的随机性,从而在平均情况下更有可能实现近似均匀的数组分割,进而提高算法的效率。
避免最坏情况:最坏情况下的时间复杂度为 O(N2),这种情况通常发生在基准值的选择不当时,例如每次都选择最大或最小的元素作为基准值。随机选择基准值能够降低最坏情况发生的概率,因为在随机选择的情况下,每次都选取最大或最小值的概率较低。
期望的平均情况:随机选择基准值能够增加算法在平均情况下的效率。数学上的期望证明表明,随机选择基准值导致数组被分割成近似相等的两部分的概率较高,因此排序的时间复杂度在平均情况下接近于 O(N*logN)
综上所述,随机选择基准值有助于提高快速排序的效率。它增加了分割的随机性,降低了最坏情况发生的概率,并在平均情况下实现了更好的性能,使得时间复杂度接近于 O(N*logN)。这种随机性导致平均情况下更为均衡的分割,从而提高了整体排序的效率。

🍏3. 代码实现

class Solution {
public:
    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(NULL));  //s->start  rand->random
        quickSort(nums,0,nums.size()-1);
        return nums;
    }
    
    void quickSort(vector<int>& nums, int l, int r)
    {
        if(l >= r)  return;

        //三路划分
        int key = getRandom(nums,l,r);
        int i = l, left = l -1, right =r + 1;
        while(i < right)
        {
            if(nums[i] < key)   swap(nums[++left],nums[i++]);
            else if(nums[i] > key)  swap(nums[--right],nums[i]);
            else    i++;
        }

        //划分完之后继续划分
        quickSort(nums,l,left);
        quickSort(nums,right,r);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r%(right - left + 1) + left];
    }

};

对排序不是和了解的,可以查看此篇文章:七大排序

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Vulnhub 靶场】【Funbox: Lunchbreaker】【简单】【20210522】

1、环境介绍 靶场介绍&#xff1a;https://www.vulnhub.com/entry/funbox-lunchbreaker,700/ 靶场下载&#xff1a;https://download.vulnhub.com/funbox/FunboxLunchbreaker.ova 靶场难度&#xff1a;简单 发布日期&#xff1a;2021年05月22日 文件大小&#xff1a;1.6 GB 靶…

java: 警告: 源发行版 17 需要目标发行版 17

这是一个编译期的报错提示 源发行版 17 , 即说明你的maven项目当前指定的编译版本是jdk17&#xff0c;需要目标发行版 17则是说明你的idea中实际选择的jdk版本并非17 检查你项目中的pom文件中的配置 <properties><java.version>17</java.version><prop…

localStorage 和sessionStorage

localStorage 和 sessionStorage 是浏览器提供的两种客户端存储数据的方式&#xff1a; 生命周期&#xff1a; localStorage&#xff1a; 存储在 localStorage 中的数据在浏览器关闭后仍然保留&#xff0c;直到被显式删除或浏览器清除缓存。sessionStorage&#xff1a; 存储在 …

2023年12月2日历史上的今天大事件早读

823年12月2日 《门罗宣言》发表 1908年12月2日 末代皇帝溥仪登基 1919年12月2日 平江开展驱除湘督张敬尧运动 1929年12月2日 北平周口店发现中国猿人头盖骨 1941年12月2日 美裔华人物理学家朱经武出生 1949年12月2日 中央决定发行人民胜利公债 1952年12月2日 拿破仑三世成…

mac 系统 vmware 安装centos8

选择镜像 安装系统 依次设置有告警的项目 设置用户名密码 设置root密码 重启系统 重启成功进入下面界面 勾选&#xff0c;点击done 点击箭头所指按钮 输入密码登录 安装成功了 设置网络 打开终端 切换root用户 输入下面指令 su root 输入root的密码 安装git

Python爬虫-新能源汽车销量榜

前言 本文是该专栏的第11篇,后面会持续分享python爬虫案例干货,记得关注。 本文以懂车平台的新能源汽车销量榜单为例,获取各车型的销量排行榜单数据。具体实现思路和详细逻辑,笔者将在正文结合完整代码进行详细介绍。 废话不多说,跟着笔者直接往下看正文详细内容。(附带…

python的制图

测试数据示例&#xff1a; day report_user_cnt report_user_cnt_2 label 2023-10-01 3 3 欺诈 2023-10-02 2 4 欺诈 2023-10-03 6 5 欺诈 2023-10-04 2 1 正常 2023-10-05 4 3 正常 2023-10-06 4 4 正常 2023-10-07 2 6 正常 2023-10-08 3 7 正常 2023-10-09 3 12 正常 2023-…

jetpack compose——圆角、渐变

一、背景圆角、渐变 效果图&#xff1a; 代码为&#xff1a; Box(modifier Modifier.clip(RoundedCornerShape(14.dp)) // 设置圆角半径.background(brush Brush.horizontalGradient( // 设置渐变色listOf(Color(0xFFF5DEC9),Color(0xFFF7A74C),))).constrainAs(box_bottom…

杨志丰:OceanBase助力企业应对数据库转型深水区挑战

11 月 16 日&#xff0c;OceanBase 在北京顺利举办 2023 年度发布会&#xff0c;正式宣布&#xff1a;将持续践行“一体化”产品战略&#xff0c;为关键业务负载打造一体化数据库。OceanBase 产品总经理杨志丰发表了《助力企业应对数据库转型深水区挑战》主题演讲。 以下为演讲…

【el-form】表单label添加?及tooltip

<el-form-item><span slot"label"><el-tooltip :content"tooltip提示框内容" placement"top"><i class"el-icon-question"></i></el-tooltip>{{ $t(menu.status) }}</span><el-radio-gr…

【1】基于多设计模式下的同步异步日志系统

1. 项目介绍 本项⽬主要实现⼀个⽇志系统&#xff0c; 其主要⽀持以下功能: • ⽀持多级别⽇志消息 • ⽀持同步⽇志和异步⽇志 • ⽀持可靠写⼊⽇志到控制台、⽂件以及滚动⽂件中 • ⽀持多线程程序并发写⽇志 • ⽀持扩展不同的⽇志落地⽬标地 2. 开发环境 • CentOS 7 • vs…

(C++)有效三角形的个数--双指针法

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://le…

旋转立方体.html(网上收集5)

<!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>旋转立方体</title><style>#cube {width: 200px;height: 200px;position: relative;transform-style: preserve-3d;animation: rotate 6s infinite linear;mar…

开发问题记录

开发问题记录&#x1f4dd; vant组件开发相关问题 vant开发的组件库初次渲染没问题,只要跳转至其他页面再进来设置的label-align属性就会丢失不生效 原因: 进入其他页面加载了主项目的vant库的css优先级层级高,然后就把组件本身的样式覆盖了, ​​​​ 解决思路: 使用渗透把主…

兼容jlink OB arm仿真器使用(杜邦线过长导致烧写总是失败)

一、兼容jlink OB的使用&#xff1a; 1、设置中要选择jlink&#xff1b; 2、模式选择SWD模式&#xff08;接三根线&#xff09;&#xff1b; 二、杜邦线过长导致stm32的stlink烧写总是失败 用ST-link烧写提示的错误信息有&#xff1a; Error while accessing a target reso…

蓝桥杯day03——Bigram 分词

1.题目 给出第一个词 first 和第二个词 second&#xff0c;考虑在某些文本 text 中可能以 "first second third" 形式出现的情况&#xff0c;其中 second 紧随 first 出现&#xff0c;third 紧随 second 出现。 对于每种这样的情况&#xff0c;将第三个词 "th…

argparse.ArgumentParser() 用法解析cmd命令行选项、参数

一、简介 1、argparse 是一个 Python 模块&#xff1a;命令行选项、参数和子命令解析器。 2、argparse 模块可以让人轻松编写用户友好的命令行接口。程序定义它需要的参数&#xff0c;然后 argparse 将弄清如何从 sys.argv 解析出那些参数。 argparse 模块还会自动生成帮助和…

三相交流电子负载的应用

三相交流电子负载可以模拟各种类型的负载&#xff0c;如电阻、电感、电容等&#xff0c;三相交流电子负载广泛应用于电力系统、工业自动化、新能源等领域&#xff0c;具有很高的实用价值。 在电力系统中&#xff0c;三相交流电子负载可以用于测试和调试电力设备。例如&#xff…

java原子类型

AtomicBoolean AtomicInteger AtomicLong AtomicReference<V> StringBuilder - 不是原子类型。StringBuilder 是 java.lang 包下的类 用法&#xff1a;无需回调改变数值

stm32项目中重定向printf打印不出来东西?三种解决方案

项目场景&#xff1a; 在stm32项目中为了调试将某些参数打出来&#xff0c;重定向printf 问题描述 printf打印不出东西 缓冲区满了才打印出来 原因分析&#xff1a; 使用printf函数必须等到缓冲区满或程序结束时&#xff0c;才进行写入到屏幕 解决方案&#xff1a; 解决方…