蓝桥杯---Topk问题（leetcode第215题）

Topk的蓝桥问题（LeetCode问题2 1 5 ）的解决方案如下： 问题描述：找到随机数组中第五大的元素。
示例： 输入：[3 ,2 ,1 ,5 ,6 ,4 ], k=2 输出：5 解释：数组排序为 [1 ,2 ,3 ,4 ,5 ,6 ]，第二大元素为 5 方法思路： 排序方法：数组排序后，直接取第 k 大元素。
快速选择算法：根据快速模式的划分概念，平均时间复杂度为O(n)。
Stack方法：使用stack或stack max来存储前k个最大的元素。
解决代码 importrandomdeffindKthLargest(nums,k):defquickselect(left, right, k_smallest): ifleft==right:returnnums[left]undi_index=random.randint(left, right) 卡 ot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest数组中最大的第 n-k 个元素。
分区函数：将数组分为两部分，左边小于基值，右边大于基值，返回到最小值的最后一个位置。
随机选择的基准值：通过随机选择图层值来优化平均时间复杂度。
递归过程：根据参考值的位置，不断处理，直到找到目标元素，判断是左半部分还是右半部分。
该方法有效地利用分区思想作为避免对数组进行完全排序的快速方法，从而提高了效率。

高效排序算法之快排

快速排序（quick sort）是一种基于分而治之思想的高效排序算法。
排序是通过递归地将数组划分为更小和更大的子数组来完成的。
平均时间复杂度为O(nlogn)，适合大规模数据排序。
1 .什么是快速排序？快速排序是基本排序算法的升级，广泛应用于计算机科学领域（如Pascal、C++等语言）。
它通过多次比较和交换来实现排序，这是高频算法题中应该掌握的经典排序方法。
2 .基本思想：分而治之策略：通过定义一个“枢轴”将矩阵分为两部分：左边部分的所有元素都小于枢轴值。
右窗格中的所有项目都大于或等于截止值。
递归排序：对除值左右两侧的子数组重复上述过程，直到子数组的长度为1 或0（即已排序）。
基本步骤：确定除法值（通常是数组中的第一个元素）。
遍历数组，将小于cutoff值的元素向左移动，大于等于的元素向右移动。
除法值的位置固定，左右子数组递归处理。
除法值的作用：每次排序后，确定除法值的位置，左边的元素都小于它，右边的元素都大于等于它。
递归终止条件：当子数组的长度为1 或0时，排序完成。
3 、代码实现（Go语言） 基本功能： 快速排序：递归调用处理左右子数组。
分区：一次性排序，确定除法值的位置，然后对数组进行分区。
funcQuickSort(a[]nums,left,rightint){ifleft>=right{return}key:=partition(a,left,right)//获取快除的值 QuickSort(a,left,key-1 )//对左子数组递归排序 QuickSort(a,key+1 ,right)//对右子数组递归排序 } funcpartition(a[]nums,left ,rightint)int{key,idx:=nums[left],left+1 //除法值是第一个元素，idx是下一个要比较的位置 forj:=left+1 ;j<=right;j++{ifnums[ j]=右）。
Partition选择除法值(nums[left])，通过遍历数组完成除法。
交换元素可确保左侧小于截止值，右侧大于或等于截止值。
返回下标分界值用于递归调用。
4 、性能分析的时间复杂度： 理想情况：每次分区将数组等分，记录迭代深度，每次排序时间为O(n)，总时间为O(nlogn)。
最坏情况：每个分区选择最小或最大的元素（如果数组已排序），递归深度为n，总时间为O(n2 )。
平均情况：可以通过随机分配截止值或“三中中间”策略来避免最坏的情况并保持 O(nlogn)。
空间复杂度：递归调用栈的空间消耗为O(logn)（理想情况）或O(n)（最坏情况）。
优化策略：三者选中间：选择nums[left]、nums[right]、nums[(left+right)/2 ]中间的值作为除法值。
随机截止值：随机选择一个项目作为截止值，以减少最坏情况的概率。
稳定性：快速排序是一种不稳定的排序算法（相同元素的相对位置可能会改变）。
适用场景：大规模数据排序（如内存数组）。
平均性能要求较高且最坏情况风险可接受的场景。
总结：快速排序通过分治推理和迭代实现高效排序。
平均时间复杂度为O(nlogn)，但要注意优化最坏情况。
其简单性和效率使其成为内部排序的首选方法之一。

找数组里第k大的数 o(你)

在查找数组中第k大的数时，可以使用的方法有全局排序、局部排序、优先队列（最小堆）、快速排序的分治法等。
全局排序：该方法对整个数组进行排序，然后直接访问排序后的数组中第k大的元素。
时间复杂度通常为 O(NlogN)，其中 N 是数组的长度。
虽然这种方法简单明了，但它并不是最高效的，因为它对整个数组进行排序，查询只需要找到第 k 大的元素。
偏排序：利用偏排序的思想，只进行k次排序，将第k大的元素放在指定位置。
时间复杂度为O(Nk)，适合k较小的情况。
k越大，效率越低。
优先级队列（最小堆）：使用最小堆数据结构来维护大小为k的堆。
迭代数组，对于每个元素，如果它大于堆顶元素，则替换堆顶元素并调整堆大小。
一旦遍历完成，堆顶元素就是第k大的元素。
时间复杂度为O(NlogK)，适合k比较小而N较大的情况。
快速排序的分而治之法：利用快速排序的思想，通过一次排序步骤将数组分为两部分。
一个部分中的元素小于另一部分中的元素。
根据参考元素的位置与k的关系，在包含第k大元素的部分递归地继续排序。
预期执行时间为 O(N)，但在最坏的情况下可能会降至 O(N^2 )。
通过一些优化技术（例如随机选择基本元素），可以降低最坏情况发生的概率。
综上所述，选择哪种方法取决于具体的应用场景和数组的大小。
在实际应用中，可以根据问题的具体要求和阵列的特点来选择最合适的算法。

几种排序方法

这两天一直在复习排序的知识，现在就整理一下目前比较常用的一些方法。
选择排序的思想是首先找到序列中最大的元素并与序列中的最后一个元素交换，然后找到第二大的元素并与倒数第二个元素交换，以此类推。
这个排序很简单，这里不再赘述。
代码实现如下： ViewCode插入排序算法流程如下： 1 、从第一个元素开始，可以认为该元素已经排序； 2 、取出下一个物品，按照排序好的物品顺序从后向前扫描； 3 、如果元素（已排序）比新元素大，则将该元素移动到下一个位置； 4 、重复步骤3 ，直到找到排序元素小于等于新元素的位置； 5 、将新元素插入到下一个位置； 6 、重复步骤2 冒泡排序的原理是依次比较相邻的两个数，小数在前，大数在后。
即第一遍：先比较第一个和第二个数，小数在前，大数在后。
然后比较第二个数和第三个数，小数在前，大数在后，如此下去，直到比较最后两个数，小数在前，大数在后。
这是第一回合结束，最大的数字留在最后。
第二轮：仍然从第一对数字开始比较（因为有可能由于第二个和第三个数字交换，第一个数字不再小于第二个数字），先放小数，再放大数，与倒数第二个数字比较（倒数第一位置已经是最大了）。
在第二遍结束时，倒数第二个位置达到了新的最大数字（实际上，它是整个序列中的第二大数字）。
如此继续，重复上述过程，直至最终排序完成。
归并排序 在介绍归并排序之前，我们首先介绍递归设计技术，称为分治法。
分治法的核心思想是：当问题比较小时，直接解决。
当问题较大时，将问题分成两个较小的子问题，每个子问题大约是原始大小的一半。
使用递归调用解决每个子问题。
递归调用完成后，常常需要进行额外的处理来组合较小问题的结果，以获得较大问题的答案。
归并排序算法在数组的中间附近分割数组，然后使用递归操作对两个半元素组成的数组进行排序，最后将两个子数组合并形成一个新的排序数组。
代码如下：ViewCode 快速排序与归并排序有很多相似之处。
将待排序数组分为两个子数组，通过两次递归调用分别对两个数组进行排序，然后将两个已排序数组合并为一个独立排序的数组。
然而，将数组分成两半比合并排序中使用的简单方法更复杂。
它必须将所有小于或等于基本元素的元素放置到基本元素前面的位置，并将大于基本元素的元素放置到基本元素后面的位置。