leetcode912.排序数组的题解

题目描述:

题目要求在不使用任何内置函数的情况下解决问题,时间复杂度为 O(nlog(n))。

笔者使用了快速排序,但是直接使用最原始的快速排序,有些特殊的测试用例会超时。

1)如果数组本身基本有序,则使用原始快速排序算法选取基准的方式,时间复杂度会退化为O(n^2),所以这里使用了随机选取基准点的方式,代码为

int randomIndex = left + rand()%(right-left+1);

swap(nums, left, randomIndex);

2)如果数组中出现了重复元素,速度也会变慢,在得到基准元素、排序之后,在递归调用排序函数前,先去除位置与基准相近、值与基准相同的元素,为什么选取基准呢?笔者认为其他位置的元素不是特别固定,选取基准后、进行一轮排序后,基准前后的元素与基准之间的大小关系是固定的,如果数组中有元素重复,那么在固定基准及其位置后,前后与基准相同的元素与数组前面或后面的大小关系也是确定的,其位置也不用调整了。

所以,最终代码是在原始快速排序基础上加上了随机选取基准点、去除重复元素,代码如下所示:

class Solution {
public:
    void swap(vector<int>& nums, int i, int j) {
        if(i == j) {
            return;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    void quicksort(vector<int>& nums, int left, int right) {
        if(left == right) {
            return;
        }
        int i = left;
        int j = right;
        int randomIndex = left + rand()%(right-left+1);
        swap(nums, left, randomIndex);
        while(i < j) {
            while((i < j) && (nums[j] >= nums[left])) {
                j--;
            }
            while((i < j) && (nums[i] <= nums[left])) {
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, left, i);
        if(i-left > 1) {
            int left_pivot = i - 1;
            while((left_pivot > left) && (nums[left_pivot] == nums[i])) {
                left_pivot--;
            }
            quicksort(nums, left, left_pivot);
        }
        if(right-i > 1) {
            int right_pivot = i + 1;
            while((right_pivot < right) && (nums[right_pivot] == nums[i])) {
                right_pivot++;
            }
            quicksort(nums, right_pivot, right);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        srand(time(0));
        quicksort(nums, 0, nums.size()-1);
        return nums;        
    }
};

思考:经典算法、前人经验当然是很好的,能够解决大部分问题,但是总有新的未知的情况出现,那么如何改进经典算法解决现有问题就是一个有趣的事情,把前人的算法理解透彻、算法的每一步的作用、新问题给现有算法带来了哪些挑战、如何改进原有算法既能不影响对于原有测试用例的处理效果又能改进对于新问题的处理效果,怎么办呢,勤学好问、多思考、多见识,把有趣的问题想清楚、弄明白,不贪多求全,找准方向、方法,刻意训练。

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

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

相关文章

迷你版VFB,极简的Freebasic开发IDE-VB7-vb6编程开发

支持Freebasic, Js, vbs, Html5开发&#xff0c;可以发布成控制台程序&#xff0c;EXE&#xff0c;标准DLL&#xff0c;OCX控件&#xff0c;网站 类似Vscode, Aardio&#xff0c;按键精灵一样的开发工具。 本来芳芳只是想做个按键精灵办公小工具&#xff0c;结果一下小心搞了一…

【综合案例】使用React编写B站评论案例

一、效果展示 默认效果&#xff0c;一开始默认按照最热进行排序 发布了一条评论 按照最新进行排序 按照最新进行排序 二、效果说明 页面上默认有3条评论&#xff0c;且一开始进入页面的时候是按照点赞数量进行倒序排列展示&#xff0c;可以点击【最热 、最新】进行排序的切换。…

SSL证书申请终极指南

SSL验证是确认网站或服务器提供的SSL 证书的真实性和有效性的过程。 SSL证书验证是确认网站或服务器提供的SSL证书的真实性和有效性的过程。SSL证书是用于在客户端&#xff08;例如Web浏览器&#xff09;和服务器之间建立安全连接的数字证书。它们对于确保通过互联网传输的数据…

处理PhotoShopCS5和CS6界面字体太小

处理PhotoShop CS6界面字体太小 背景&#xff1a;安装PhotoShop CS6后发现无法调大字体大小&#xff0c;特别是我的笔记本14寸的&#xff0c;显示的字体小到离谱。 百度好多什么降低该电脑分辨率&#xff0c;更改电脑的显示图标大小&#xff0c;或者PS里的首选项中的界面设置。…

python中t是什么意思

python中t是什么意思&#xff1f; python中t指的是“\r”&#xff1a;回车符&#xff0c;返回到这一行的开头&#xff0c;return的意思。 其他相关&#xff1a; \n&#xff1a;换行符&#xff0c;到下一行的同一位置&#xff0c;纵坐标相同&#xff0c;new line的意思。 \t…

python项目实战---使用图形化界面下载音乐

音乐下载 设计思路&#xff1a; 设计界面编写爬虫代码绑定爬虫打包exe文件 这个是最终的设计成果&#xff0c;所有的下载歌曲都在“下载mp3”文件夹里面 完整代码 逻辑代码 import os.path import reimport requests from PyQt5.QtWidgets import QApplication,QWidget,QM…

Linux(inode + 软硬链接 图片+大白话)

后面也会持续更新&#xff0c;学到新东西会在其中补充。 建议按顺序食用&#xff0c;欢迎批评或者交流&#xff01; 缺什么东西欢迎评论&#xff01;我都会及时修改的&#xff01; 在这里真的很感谢这位老师的教学视频让迷茫的我找到了很好的学习视频 王晓春老师的个人空间…

从0开始深度学习(24)——填充和步幅

1 填充 在上一节中&#xff0c;我们的卷积步骤如下&#xff1a; 可以发现输入是 3 3 3\times3 33&#xff0c;输出是 2 2 2\times2 22&#xff0c;这样可能会导致原始图像的边界丢失了许多有用信息&#xff0c;如果应用多层卷积核&#xff0c;累积丢失的像素就更多了&#…

C++:模拟实现STL的vector

目录 一.vector类 1.vector类的构造及析构 2.定义迭代器 3.size()和capacity() 4.operator [ ] 5.resize()和reserve() 6.插入和删除 二.整体代码 1.vector.h 2.vector.cpp 上一节中了解了vector中部分接口的使用,在这里我们模拟实现vector,为了避免与库中的起冲突,…

砥砺十年风雨路,向新而行创新程丨怿星科技十周年庆典回顾

10月24日&#xff0c;是一年中的第256天&#xff0c;也是程序员节&#xff0c;同时也是怿星的生日。2014年到2024年&#xff0c;年华似水匆匆一瞥&#xff0c;多少岁月轻描淡写&#xff0c;怿星人欢聚一堂&#xff0c;共同为怿星科技的十周年庆生&#xff01; 01.回忆往昔&…

Chrome与火狐哪个浏览器的移动版本更流畅

在当今的数字化时代&#xff0c;移动设备已经成为我们生活中不可或缺的一部分。而浏览器作为我们访问互联网的重要工具&#xff0c;其性能和用户体验直接影响到我们的使用感受。本文将对比Chrome和火狐&#xff08;Firefox&#xff09;两款主流浏览器的移动版本&#xff0c;探讨…

算法练习:1004. 最大连续1的个数 III

题目链接&#xff1a;1004. 最大连续1的个数 III。 题目要求&#xff0c;给定一个数组&#xff0c;这个数组里面只有0或1&#xff0c;然后计算有多少个连续的1的最大长度&#xff0c;同时给了一个条件就是&#xff0c;可以把k个0变成1&#xff0c;然后来计算长度。 暴力解法&a…

【大数据技术基础 | 实验七】HBase实验:部署HBase

文章目录 一、实验目的二、实验要求三、实验原理四、实验环境五、实验内容和步骤&#xff08;一&#xff09;验证Hadoop和ZooKeeper已启动&#xff08;二&#xff09;修改HBase配置文件&#xff08;三&#xff09;启动并验证HBase 六、实验结果七、实验心得 一、实验目的 掌握…

LLMs之LoLCATs:《LoLCATs: On Low-Rank Linearizing of Large Language Models》翻译与解读

LLMs之LoLCATs&#xff1a;《LoLCATs: On Low-Rank Linearizing of Large Language Models》翻译与解读 导读&#xff1a;这篇论文的核心是提出了一种名为 LoLCATs (Low-rank Linear Conversion via Attention Transfer) 的方法&#xff0c;用于高效地将大型语言模型 (LLM) 线性…

linux命令详解,文件管理类

文件管理 stat 显示文件的详细信息&#xff0c;包括时间戳 stat filenametouch 主要用于更新文件的访问时间和修改时间&#xff08;时间戳&#xff09;。如果指定的文件不存在&#xff0c;touch 命令会创建一个新的空文件。 touch newfile参数 -t 更新文件的修改时间为特…

MySQL的其他函数

数学函数&#xff1a; 1.round 四舍五入 select round(1.45);//不管正负数,先将绝对值round,然后加正负号 select round(1.567,2); //表示小数点保留2位 2.ceil 向上取整 select ceil(-1.3); 3.floor 向下取整 4.truncate 截断 select truncate(1.65,1); // 结果保留小数…

@Excel若依导出异常/解决BusinessBaseEntity里面的字段不支持导出

今天发现所有实体类继承BusinessBaseEntity里面的这些通用字段不支持导出&#xff0c;debug时发现是这样&#xff1a; 导出效果 这里我把能查到的方法都汇总了&#xff0c;如果你也遇到这个异常&#xff0c;可以去逐步排查 1.先看库里有没有数据 2.看字段名是否对齐 3.所需要…

云数据中心基础环境-详细设计方案(364页WORD)

文档介绍&#xff1a; 随着云计算技术的飞速发展&#xff0c;云数据中心已成为企业数字化转型的核心基础设施&#xff0c;承载着数据存储、处理、分析和应用的重任。本设计方案旨在构建一个高性能、高可用、高安全性的云数据中心基础环境&#xff0c;以满足企业日益增长的业务需…

在 CSS 中,gap 是 布局容器(flex 或 grid)的属性。它用于设置容器内子元素之间的间距。

在 CSS 中&#xff0c;gap 是 布局容器&#xff08;flex 或 grid&#xff09;的属性。它用于设置容器内子元素之间的间距。以下是 gap 属性在不同布局中的应用&#xff1a; 1. 在 CSS Grid 布局中 gap 定义了网格行和列之间的间距。可以分别使用 row-gap 和 column-gap 设置行…

Python练习9

Python日常练习 题目&#xff1a; 编程序计算形式如&#xff1a;sumaaaaaaaaaa…aaa…aaa的表达式的值。 说明&#xff1a; 补充完整函数fun()&#xff0c;其中a为小于10的自然数&#xff0c;n为项数&#xff0c;给定 变量result作为函数返回值&#xff0c;变量ts作为…