查找第K大元素

2019-11-10 19:33:08

字体：大中小

来源：转载

供稿：网友

查找第k大元素

问题描述

给定一个无需数组a,长度为n,以及一个整数k（0

问题分析

首先大家能够想到的，就是把数组进行排序，然后找出下标为k的元素。如果是用快速排序，那么整个过程的时间复杂度是O(nlogn)，显然不够好。接着上面的分析，如果用快速排序，但是明显我们这个题目不需要把整个数组都排序，只需要排一部分就可以了（在代码中能够体会到）。好，我们就在快排的基础上改进一下。

不了解快速排序的话，可以看快速排序，快速搞定

算法描述

首先通过轴值（pivot）将数组分为两半，这时候轴值左边的都比轴值小，右边的都大于等于轴值。设最终轴值的位置是p，那么轴值一定是数组中第p大元素（仔细读上句话）。举例：a = {4,3,2,1,5,6,7,8,9} 我们选取a[0](4)为轴值，那么将数组划分后，得：a = {3,2,1,4,5,6,7,8,9}，这时候轴值4的位置是3，我们可以看到，第三大的数就是4。那么我们可以通过轴值的位置与k进行比较，如果k==p，那么a[p]就是第k大的数了。如果k> p，那么轴值一定在[p+1,n]的范围，所以我们只需要对右边进行递归就好。如果k< p，只需要对左边进行递归。

代码

//查找第k大的元素为了简便起见 k从0开始 public static int findKth(int[] a,int first,int last,int k){ if(first == last){ return a[first]; } int pivot = a[first];//轴值 int left = first , right = last; while(left!=right){ while(a[right]>=pivot && right!=left){ right--; } a[left] = a[right]; while (a[left]<pivot && right!=left){ left++; } a[right] = a[left]; } a[left] = pivot;//轴值的位置 if(left == k){ return pivot; } if(left>k){ return findKth(a,0,left-1,k); }else { return findKth(a,right+1,a.length-1,k); } }

上一篇：leecode 解题总结：33. Search in Rotated Sorted Array

下一篇：spring.profiles.active配置多种spring启动环境

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注