做360网站优化快速,株洲网站制作公司,专门做行业分析的网站,北京微信网站建设一.前置条件 假如数组为a,大小为n#xff0c;要找到数组a中第k大的数。
二.解决方案 1.使用任意一种排序算法#xff08;例如快速排序#xff09;将数组a进行从大到小的排序#xff0c;则第n-k个数即为答案。 2.构造一个长度为k的数组#xff0c;将前k个数复制过来并降序…
一.前置条件 假如数组为a,大小为n要找到数组a中第k大的数。
二.解决方案 1.使用任意一种排序算法例如快速排序将数组a进行从大到小的排序则第n-k个数即为答案。 2.构造一个长度为k的数组将前k个数复制过来并降序排序。然后依次将 k1 到 n 位的数分别插入 k 长度的数组中并保持数组长度为k且降序排列。最终长度为k的数组的最后一个元素即是答案。 3.将数组的所有元素构造一个大顶堆然后删除堆顶元素k次并重新构成大顶堆则第k次操作后的堆顶元素即为答案。 4.用快速排序的思想不把数组元素全排序的优化算法。 1先看一下快速排序降序排序的算法。
/**
快速排序主函数
a要排序的数组
left排序数组左边界索引
right排序数组右边界索引
*/
public void quickSort(int a[], int left, int right) {if (left right) {//算出基准元素索引值indexint index partition(a, left, right);//对低于index索引的数组递归排序quickSort(a, left, index - 1);//对高于index索引的数组递归排序quickSort(a, index 1, right);}}//算出基准元素索引值此索引值左侧值都大于基准元素值此索引值右侧值都小于基准元素值
public int partition(int[] num, int left, int right) {if (num null || num.length 0 || left 0 || right num.length) {return 0;}//获取数组基准元素的下标int prio num[left (right - left) / 2]; //从两端交替向中间扫描 while (left right) { while (num[left] prio)left;while (num[right] prio)right--;if (left right) {//将不符合条件的元素值交换位置并继续扫描swap(num, left, right); left;right--;}}return left;
}//交换元素
public void swap(int[] num, int left, int right) {int temp num[left];num[left] num[right];num[right] temp;
}
2我们选择数组区间 a[0…n-1]的中间位置的一个元素 a[n/2]作为 pivot对数组 a[0…n-1]进行分区这样数组就分成了三部分a[0…p-1]、a[p]、a[p1…n-1]。 如果 p1k那 a[p]就是要求解的答案如果 kp1, 说明第 k 大元素出现在 a[p1…n-1]区间我们再按照上面的思路递归的在 a[p1…n-1]这个区间内查找。同理如果 kp1那就在 a[0…p-1]区间内递归查找。
3所以改进后的代码如下
public int quickSortKthLargest(int a[], int left, int right, int k) {if (left right) {//算出基准元素索引值indexint index partition(a, left, right);//索引对应的值就是第k大的数if(index1k){return a[index];}//在索引左边继续查找else if(index1k){return quickSortKthLargest(a, left, index-1, k);} //在索引右边继续查找else{return quickSortKthLargest(a, index1, right, k);}}else{return -1;}} 5.在Python中我们可以使用内置的heapq库来查找数组的第k大元素。heapq库实现了一个堆数据结构我们可以利用堆的性质来找到数组的第k大元素。 代码如下
# 返回第k大元素
def get_kth_largest(a, k): # heapq.nlargest(k, a)会返回数组a中最大的k个元素# 然后我们通过[-1]来取得这k个元素中的最后一个也就是第k大的元素。return heapq.nlargest(k, a)[-1] 6.使用最小堆来查找第k大的元素。 首先构建一个空的最小堆。遍历数组a如果堆的大小小于k我们就把当前元素加入堆中。如果堆的大小已经达到了k我们就比较当前元素和堆顶元素也就是堆中的最小元素如果当前元素大于堆顶元素我们就把堆顶元素替换为当前元素再重新调整最小堆结构。这样当遍历完整个数组后堆顶元素就是数组的第k大元素即是大小为k的最小堆保存了数组中的最大的k个数的最小元素。 代码如下
def get_kth_largest(a, k): heap [] for num in a: # 若最小堆大小小于k则将元素插入最小堆if len(heap) k: heapq.heappush(heap, num) else: # 若元素大于最小堆堆顶元素则插入最小堆并重新排列if num heap[0]: heapq.heapreplace(heap, num) # 堆顶元素即为数组的第k大元素return heap[0] 致力于C、C、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。
若作品对您有帮助请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。
