如何用一个循环求出一个数组中第二大的数

可能没有讲明白,这里重新说一下

定义两个变量max1,max2分别代表第一大和第二大的数字,我们将前两个数字大的放在max1,小的放在max2;从需要遍历的第三个数字开始,如果当前数字比max2大,max2=当前数字,比较一下max1和max2,如果max1小于max2,交换一下max1和max2

之前从max1开始比较需要比较一遍max2现在这种思想比较好理解一点本质上就是用堆求topk的问题

原则上时间复杂度是nlogk,因为这里k是2,所以logk=1(一个常数),时间复杂度为O(Cn)=O(n)

qlibtrade是一个开源的量化交易平台，它没有固定的交易时间。交易时间取决于所连接的交易所的交易时间。不同的交易所有不同的交易时间，例如，中国股市的交易时间是周一到周五的上午9:30到下午3:00。如果你使用qlibtrade连接的是中国股市，那么交易时间就是按照中国股市的交易时间来进行的。

思路：

（1）可以避免对所有数据进行排序，只排序部分；

（2） 冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK。

时间复杂度空间复杂度：（1）时间复杂度：排序一轮是O(N)，则K次排序总时间复杂度为：O(KN)。（2）空间复杂度：O(K)，用来存放获得的topK，也可以O(1)遍历原数组的最后K个元素即可。

思路：

（1）堆：分为大顶堆（堆顶元素大于其他所有元素）和小顶堆（堆顶其他元素小于所有其他元素）。

（2）我们使用小顶堆来实现。

（3） 取出K个元素放在另外的数组中，对这K个元素进行建堆。

（4） 然后循环从K下标位置遍历数据，只要元素大于堆顶，我们就将堆顶赋值为该元素，然后重新调整为小顶堆。

（5） 循环完毕后，K个元素的堆数组就是我们所需要的TopK。

时间复杂度与空间复杂度：

（1）时间复杂度：每次对K个元素进行建堆，时间复杂度为：O(KlogK)，加上N-K次的循环，则总时间复杂度为O((K+(N-K))logK)，即O(NlogK)，其中K为想要获取的TopK的数量N为总数据量。

（2）空间复杂度：O(K)，只需要新建一个K大小的数组用来存储topK即可

思路：

（1）比如有10亿的数据，找处Top1000 ，我们先将10亿的数据分成1000份，每份100万条数据。

（2） 在每一份中找出对应的Top 1000，整合到一个数组中，得到100万条数据，这样过滤掉了999%%的数据。

（3） 使用快速排序对这100万条数据进行”一轮“排序，一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分，一部分大于S记作Si，一部分小于S记作Sj。

（4） 如果Si元素个数大于1000，我们对Si数组再进行一轮排序，再次将Si分成了Si和Sj。如果Si的元素小于1000，则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序（5）如此递归下去即可获得TopK。

时间复杂度与空间复杂度：

（1）时间复杂度：一份获取前TopK的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)，但是分治法我们会使用多核多机的资源，比如我们有S个线程同时处理。则时间复杂度为：O((N/S)logK)。之后进行快排序，一次的时间复杂度为：O(N),假设排序了M次之后得到结果，则时间复杂度为：O(MN)。所以 ，总时间复杂度大约为O(MN+(N/S)logK) 。

（2）空间复杂度：需要每一份一个数组，则空间复杂度为O(N)。

可以利用堆、外排序的方法来做多个处理单元的结果合并

堆，其实就是一个完全二叉树；

完全二叉树，要么是一个满二叉树，要么叶子节点层为从左到右；

堆，实际中是可以用数组实现的；

规律，把数组脑补成完全二叉树

节点 n 的左孩子为 2n + 1 ,也就是 n<<1 +1

节点 n 的左孩子为 2n + 2 ,也就是 n<<1 +2

节点 n 的父节点为 (n-1)/2 ,也就是 (n-1)>>2

堆分为小根堆、大根堆

小根堆：在完全二叉树中， 任何一个子树 的最小值都在头部，小根堆，数组最小值在 arr[0]

大根堆：在完全二叉树中， 任何一个子树 的最大值都在头部，大根堆，数组最大值在 arr[0]

思想：1、根据大根堆的特点，先将一个数组构建成为一个大根堆，这样堆顶就是最大的

2、再将堆顶和最后一个数互换，将最大的数放到最后，随即调整维持大根堆

继续互换、调整。

java实现的堆结构、优先级队列， PriorityQueue()

PriorityQueue当size达到了初始的initialCapacity容量后会进行扩容，每次容量加1。

1->1

1,2->15

1,2,3->2

准备一个大根堆，一个小根堆

把小于等于大根堆对顶的树插入大根堆，

把大于大根堆对顶的树插入小根堆；

同时，要调整大根堆和小根堆的数量，数量差值不要超过1；

如果大根堆的size大了，就把大根堆 的堆顶取出插入小根堆；

如果小根堆的size大了，就把小根堆 的堆顶取出插入大根堆；

这样就能达到，大根堆，小根堆数量保持平衡，同时大根堆中的小的n/2个数，小根堆中是大的n/2个数，

（大根堆堆顶+小根堆堆顶）/2 就是流的中位数

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。

思路： 利用一个小根堆，把每个文件的第一条记录取出来，放入小根堆中，那么小根堆的堆顶就是这100条记录中顺序最小的记，它为记录A，也是这100个文件中顺序最小的，将这个堆顶追加到准备的大文件。从记录A原来所在的文件中再取出一条记录，放入小根堆，取出堆顶，如此重复

思路： 利用一个size为k的堆，求最大的Top K 用小根堆 ，求最小的Top k用大根堆。

我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

遍历数组需要 O(n) 的时间复杂度，一次堆化 *** 作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK)。

使用map<key,count>计数，count放入小根堆中，多个小根堆合并求top10

分析：假设一条搜索50个字节，10亿条那么就占用了50GB的大小，所以一次对所有数据进行统计是不可行的。

0、准备10个空文件

1、采用hash 算法将日志进行计算之后得到hash值，模10，存放入对应的文件中。那么每个文件大概会有1亿条记录，假设平均每条关键词重复10次，那么就是1000万条关键词，大概500MB，1G的内存是可以存下的

2、使用hashmap对每个小文件中的关键词进行数量统计，对每个小文件的统计的结果存入一个Size为10 的小根堆。

3、对这10个小根堆再进行合并得到最终的Top 10 的搜索关键词

推荐阅读：

数据结构和算法|堆的应用

以上就是关于如何用一个循环求出一个数组中第二大的数全部的内容，包括:如何用一个循环求出一个数组中第二大的数、qlibtrade时间、topK的3种解法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！