对于队列最好的方法是使用链表实现，因为对于数组来说，队列可能会出现下面这种情况： ? 如图所示，不可以继续添加元素，否则会造成数组越界而遭致程序出错。...然而此时又不应该扩充数组，因为还有大量实际空间未被占用。 此时我们应该如何解决这个问题呢？我们将其实现为循环队列。 理解循环队列 何谓循环队列？首先我们要说明的是循环队列仍然是基于数组实现的。...3.我们把它掰弯，用的是求余，这样两个值就不会跑出最大范围，并且可以实现弯曲的效果，所以说对于循环队列我们必须给定最大值MAXQSIZE。...这其实是我们臆想的，反正我们要做的就是利用循环来解决空间浪费的问题。 循环队列的实现过程 ? 当添加一个元素时,(rear+1)%MAXQSIZE; //理解为什么求余？...当删除一个元素时,(front+1)%MAXQSIZE；//理解为什么求余？ 当rear=front的时候，队列可能是满，也可能是空。
这和什么是数据结构那篇文章中讲到的姓名按拼音顺序排列的电话簿类似。 数组 ?...如上就是数组的概念图，Blue、Yellow、Red 作为数据存储在数组中，其中 a 是数组的名字，后面 [] 中的数字表示该数据是数组中的第几个数据，该数字也就是数组下标，下标从 0 开始计数，比如...那么为什么许多编程语言中的数组都从 0 开始编号的呢？先别急，可以先自己思考下，将会在文末进行讲解。 ? 从图中可以看出来，数组的数据是按顺序存储在内存的连续空间内的。 ?...最后，让我们一起来思考下刚开始提到的问题：为什么很多编程语言中数组都从 0 开始编号？ 解惑 从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。...有一种高效的查找算法是二分查找法，就是利用了数组随机访问的特性。 总得来说，数组适用于多操作多、写操作少的场景，和我们上一篇文章中的链表正好相反。
以刚才的数列为例，统计数组的长度为 99-90+1 = 10 ，偏移量等于数列的最小值 90 。 对于第一个整数95，对应的统计数组下标是 95-90 = 5，如图所示： ? ? ? 什么意思呢？...给定一个学生的成绩表，要求按成绩从低到高排序，如果成绩相同，则遵循原表固有顺序。 那么，当我们填充统计数组以后，我们只知道有两个成绩并列95分的小伙伴，却不知道哪一个是小红，哪一个是小绿： ? ?...我们仍然以刚才的学生成绩表为例，把之前的统计数组变形成下面的样子： ? 这是如何变形的呢？统计数组从第二个元素开始，每一个元素都加上前面所有元素之和。 为什么要相加呢？...初次看到的小伙伴可能会觉得莫名其妙。 因为原来的统计数组（未变形）里面存储的是各个元素的个数，那么向后叠加的目的就是为了计算元素排序后的最终位置（准确来说是最大的最终位置）。...变形后的统计数组（countArray）中的值就代表着原数列元素排序后最大的最终位置（在重复元素的情况下还会有其他相同元素在此位置之前）。比如下标是5的值为4，说明 95 排序后的位置最大就是第四。
概念 快速排序的基本思想是基于分治法的，在待排序表中任选一个基准元素，通过一趟排序将待排序划分为独立的两部分，前半部分所有元素均比枢轴元素小，后半部分所有元素均比枢轴元素大，此时枢轴元素就放在了最终的位置...算法实现 快速排序比冒泡排序优良的地方在于它的每次比较不是相邻元素的一次一次比较，而分别从两端开始”探测”的，先从右往左找一个小于枢轴元素的数，放到枢轴的左边，再从左往右找一个大于枢轴的数，放在枢轴的右边...a[low]>temporary) low++; a[high]=a[low]; } a[low]=temporary; return low; } 快速排序的效率相对而言比较优良...快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或者基本逆序时，就得到最坏情况下的时间复杂度...快速排序是所有内部排序算法中平均性能最优的排序算法。是一种不稳定的排序方法。 在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴元素放在其最终的位置上。
这世上有三样东西是别人抢不走的：一是吃进胃里的食物，二是藏在心中的梦想，三是读进大脑的书 为什么处理排序的数组要比非排序的快 问题 以下是c++的一段非常神奇的代码。...---- 我首先得想法是排序把数据放到了cache中，但是我下一个想法是我之前的想法是多么傻啊，因为这个数组刚刚被构造。 到底这是为什么呢？ 为什么排序的数组会快于没有排序的数组？...这段代码是为了求一些无关联的数据的和，排不排序应该没有关系啊。 回答 什么是分支预测？...TTTTTTTTTT (easy to predict) 但是当数据是完全随机的，分支预测就没什么用了。因为他无法预测随机的数据。因此就会有大概50%的概率预测出错。...一般的建议是尽量避免在关键循环上出现对数据很依赖的分支。
不熟悉计数排序的读者可以先看这篇文章： 什么是计数排序？ ? ? ? ———————————— ? ? ? ? ? ?...让我们先来回顾一下计数排序： 计数排序需要根据原始数列的取值范围，创建一个统计数组，用来统计原始数列中每一个可能的整数值所出现的次数。...原始数列中的元素（整数），和统计数组的下标是一一对应的，以数列的最小值作为偏移量。比如原始数列的最小值是90， 那么整数95对应的统计数组下标就是 95-90 = 5。 ?...那么，桶排序当中所谓的“桶”，又是什么概念呢？ 每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。桶排序的第一步，就是创建这些桶，确定每一个桶的区间范围： ?...Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种时间复杂度 O（nlogn）的排序。 ? ?
介绍 希尔排序又称缩小增量排序，基本思想为：先将待排序列分割成若干子表，把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表已基本有序的时候，再对整个表进行一次直接插入排序。...算法实现 实现方法1（我编写的我认为容易理解的希尔排序实现算法） 我们初始时，令增量d为数组大小的一半，之后每次增量折半，直到小于1的时候，会停止。...也就是最后一次循环时，增量为1，相当于直接插入排序，但此时因为已经基本有序，所以移动的元素非常少了。 每个增量dt将元素分成dt组，每组的元素进行直接排序。...，我认为是最容易理解，但效率不是最高的，程序中使用了四重循环。...，实现方法因人而异，我们不需要纠结到底哪一个效率最高，因为只要是按照此算法理解实现的程序，大致的算法时间复杂度都大同小异，关键是我们是否能学会此算法，而判断我们学会算法的标准就是自己能写出符合此算法思路的实现程序
外部排序的基本概念 在内存中进行的排序是内部排序，而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。...因为磁盘读 / 写的机械动作所需的时间远远超过内存运算的时间（相对而言可以忽略不记），因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。 外部排序通常采用归并排序法。...它包括两个相对独立的阶段： 根据内存缓冲区大小，将外存上的文件分成若干长度为t的子文件，依次读入内存并利用内部排序方法对他们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串...对这些归并段进行逐趟归并，是归并段逐渐由小到大，直至得到整个有序文件位置。...一般情况下： 外部排序的总时间 = 内存排序所需的时间 + 外存信息读取的时间 + 内部归并所需的时间 显然，外村信息读取地时间远大于内部排序和内部归并地的时间，因此应着力减少I/O次数。
前言 Spring如何解决的循环依赖，是女同事今天问我的一个问题，其实我很早之前就知道了，但是又有点不知道细节了，那不放大家跟丙丙一起回顾一下。 其实敖丙本人对这类框架源码题还是持一定的怀疑态度的。...如果敖丙作为面试官，可能会问一些诸如“如果注入的属性为null，你会从哪几个方向去排查”这些场景题。...那么既然写了这篇文章，闲话少说，发车看看Spring是如何解决的循环依赖，以及带大家看清循环依赖的本质是什么。...正文 通常来说，如果问Spring内部如何解决循环依赖，一定是单默认的单例Bean中，属性互相引用的场景。 比如几个Bean之间的互相引用： 甚至自己“循环”依赖自己：
什么是事件循环 Eventloop 同步编程 我们先不着急明白事件循环是什么。先从它的起源入手。...大家都知道JavaScript是同步的，也就是单线程，原因是因为如果不使用单线程，在操作DOM时可能会出现一些问题，比如我们有两个事件，一个是删除div，一个是添加div，他们的执行顺序不同，导致的结果也将截然不同...于是JavaScript就有了异步任务的概念。 所谓的异步任务，和同步任务不同，同步任务是一个任务和它的回调函数完成了，才执行下一个任务。...事件循环 eventloop 说了这么多，那事件循环究竟是什么呢？事件循环，简单理解就是代码的执行流程。而理解事件循环就是理解所谓的同步代码、异步代码或者说宏任务、微任务的执行的先后顺序。...（3）开启下一轮循环后，重复上诉操作，注意每个setTimeout本身是一个宏任务，而非多个setTimeout为一个宏任务。
问题描述： 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。 找到所有出现两次的元素。...示例： 输入: [4,3,2,7,8,2,3,1] 输出: [2,3] 按照循环排序思想： class Solution: def findDuplicates(self, nums: List
背景 西天取经的路上，一样上演着编程的乐趣..... ? ? ? ? ? ? ? 排序的时候我们可以选择快速排序或归并排序等算法。为了方便，我们把排序好的2G有序数据称之为有序子串吧。...接着我们可以把两个小的有序子串合并成一个大的有序子串。 ? 注意：读取的时候是每次读取一个int数，通过比较之后在输出。 按照这个方法来回合并，总共经过三次合并之后就可以得到8G的有序子串。 ? ?...这里说明一下，那个被放在一边的数是不能再放入p1中的了，因为它一定比p1中的数都要小，所以它会放在下一个子串中 看这些文字会让人头大，我画图解释下吧。 从12数据读取3个数据 ?...此时p1已经完成了，把那些刚才暂放一边的数重新构成一个堆，继续p2的存放。 ? 以此类推... 最后生成的p2如下： ? ? ? ? ? 这种方法适合要排序的数据太多，以至于内存一次性装载不下。...只能通过把数据分几次的方式来排序，我们也把这种方法称之为外部排序 ?
桶排序和计数排序一样，不受O(nlogn)时间复杂度下限的影响，它将待排序序列通过遍历方式分到有限数量的桶中，然后每个桶被单独地排序，不管是使用同一个比较类排序算法或者使用不同的排序算法，或者还是递归地使用桶排序...数组中第一个元素是13，进行(13 - min) / 10的运算，得2，放入到第3个桶；数组中第2个元素是9，(9 - min) / 10 = 0，放入到第1个桶；依此类推。...我们采用HashMap的方式记录桶的情况，每次将数组中的元素输入到情况去，得到的分桶值作为key，添加元素的动态数组对象作为value。...-----END----- 推荐阅读： 动画 | 什么是计数排序？ 动画 | 什么是归并排序？ 动画 | 什么是堆排序？ 动画 | 什么是选择排序？ 动画 | 什么是希尔排序？...动画 | 什么是插入排序？ 动画 | 什么是快速排序？ 动画 | 冒泡排序只是简单的冒泡排序吗？
————— 第二天 ————— ———————————— 我们假定要获得升序数列，冒泡排序的原理是什么呢？...顾名思义，就是把每一元素和下一个元素进行比较和交换，使得较大的元素像气泡一样向右侧移动： 这样一来，每一轮操作都可以把一个最大元素移动到最右侧，经过多轮操作，无序的数列成为了升序数列： 这就是冒泡排序的基本原理...如果是按照冒泡排序的思路来指挥，结果会是什么样子呢？ 如此一来，同学们一共交换了4次，还只是完成了冒泡排序的第一轮操作。如果继续下去，同学们心里恐怕会想：“这体育老师是不是有毛病啊？”...在程序运行的世界里，虽然计算机并不会产生什么“负面情绪”，但是频繁的数组元素交换意味着更多的内存读写操作，严重影响了代码运行效率。...让我们来看一下具体的指挥过程： 如此一来，只需要很少的交换次数就可以完成队伍的排序，老师和同学们皆大欢喜。
在上一篇漫画中，小灰介绍了 二叉堆 这样一种强大的数据结构： 漫画：什么是二叉堆？（修正版） 那么，这个二叉堆怎样来使用呢？我们这一期将会详细讲述。...之前说过二叉堆实际存储在数组当中，数组中的元素排列如下： 由此，我们可以归纳出堆排序算法的步骤： 1. 把无序数组构建成二叉堆。 2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。...（downAdjust 方法）是堆排序算法的基础，这个调节操作本身的时间复杂度是多少呢？...假设二叉堆总共有n个元素，那么下沉调整的最坏时间复杂度就等同于二叉堆的高度，也就是O（logn）。 我们再来回顾一下堆排序算法的步骤： 1. 把无序数组构建成二叉堆。 2....循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。 第一步，把无序数组构建成二叉堆，需要进行n/2次循环。
计数排序 计数排序（Counting Sort）是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量（类似于哈希映射），然后对映射后的数组进行排序输出即可。...回答了这个问题，稳定的计数排序也就彻底理解了~~ 第一步：从后向前遍历，具体为什么是从后向前，看完了你就会明白了！...以此类推，就可以得到原数组 arr[] 中每一个元素在排序后的正确位置 这就是稳定的计数排序，那我们再来回答一下为什么从后向前遍历新的 count[] 数组？ 因为只有这样才能保证计数排序的稳定性！...for 循环，没有出现任何 for 循环的嵌套，所以计数排序的时间复杂度为 量级。...优缺点分析 如果输入数据的范围 range = max - min + 1 不明显大于要待排序数组的长度 n = arr.length，则计数排序是相当高效的，比时间复杂度为 的快速和归并排序都优秀
这篇文章用漫画的形式讲解了基数排序，通俗易懂。 ? ? ————— 第二天 ————— ? ? ? ? ? ? ? ———————————— ? ? ? ? ? ? 什么是计数排序呢？...由于这些整数的范围是从0到10这11个数，我们可以创建一个长度11的空数组，数组从0到10的下标，对应着待排序的随机整数值0到10： ?...这就是计数排序的朴素版本。 为了实现稳定排序（排序后，相等元素原本的先后顺序不变），真正的计数排序要稍微复杂一些，感兴趣的小伙伴可以读一读这篇： 漫画：什么是计数排序？ ? ?...，循环进行k次，k就是数组中最长字符串元素的字符数。...在循环体内，执行的是计数排序的逻辑。这个稳定的计数排序算法不太好理解，在小灰往期的漫画中有进行详细讲解（漫画：什么是计数排序？）。 ? ? ? ? ?
以刚才的数列为例，统计数组的长度为 99-90+1 = 10 ，偏移量等于数列的最小值 90 。 对于第一个整数95，对应的统计数组下标是 95-90 = 5，如图所示： ? ? ? 什么意思呢？...给定一个学生的成绩表，要求按成绩从低到高排序，如果成绩相同，则遵循原表固有顺序。 那么，当我们填充统计数组以后，我们只知道有两个成绩并列95分的小伙伴，却不知道哪一个是小红，哪一个是小绿： ? ?...我们仍然以刚才的学生成绩表为例，把之前的统计数组变形成下面的样子： ? 这是如何变形的呢？统计数组从第二个元素开始，每一个元素都加上前面所有元素之和。 为什么要相加呢？...初次看到的小伙伴可能会觉得莫名其妙。 这样相加的目的，是让统计数组存储的元素值，等于相应整数的最终排序位置。比如下标是9的元素值为5，代表原始数列的整数9，最终的排序是在第5位。...这样一来，同样是95分的小红和小绿就能够清楚地排出顺序了，也正因此，优化版本的计数排序属于稳定排序。 后面的遍历过程以此类推，这里就不再详细描述了。 ? ?
我们可以有这样的思路，对于任何一个待排序数组的元素x，如果知道了待排序数组中有多少个元素比x小，就可以直接知道排序后x应该在什么位置上。...例如，知道了待排序数组有5个元素比7小，就可以知道7在排序后是在第6个位置，对应的下标为5。 那什么知道数组中有多少个元素比x小呢？如果为了期望时间复杂度为线性时间，这种时候不可能去做比较计算。...为了保证待排序列的稳定性，从数组a最后一个元素出发，根据数组c可以看到7是在第8个位置，可以设置要输出的数组b，长度和数组a一样。...不过代码量确实不如比较排序类的简单。 ——END—— 推荐阅读： 动画 | 什么是归并排序？ 动画 | 什么是堆排序？ 动画 | 什么是选择排序？ 动画 | 什么是希尔排序？...动画 | 什么是插入排序？ 动画 | 什么是快速排序？ 动画 | 什么是冒泡排序？
最终，数列遍历完毕时，数组的状态如下： 数组每一个下标位置的值，代表了数列中对应整数出现的次数。 有了这个“统计结果”，排序就很简单了。...以刚才的数列为例，统计数组的长度为 99-90+1 = 10 ，偏移量等于数列的最小值 90 。 对于第一个整数95，对应的统计数组下标是 95-90 = 5，如图所示： 什么意思呢？...我们仍然以刚才的学生成绩表为例，把之前的统计数组变形成下面的样子： 这是如何变形的呢？统计数组从第二个元素开始，每一个元素都加上前面所有元素之和。 为什么要相加呢？...初次看到的小伙伴可能会觉得莫名其妙。 这样相加的目的，是让统计数组存储的元素值，等于相应整数的最终排序位置。比如下标是9的元素值为5，代表原始数列的整数9，最终的排序是在第5位。...这样一来，同样是95分的小红和小绿就能够清楚地排出顺序了，也正因此，优化版本的计数排序属于稳定排序。 后面的遍历过程以此类推，这里就不再详细描述了。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
云直播
对象存储
腾讯会议
