# LeetCode215.数组中的第K个最大元素

#### 题目链接：LeetCode215

第一种做法，直接排序完了取,时间复杂度O(logn)

```class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}```

第二种做法，BFPRT算法，时间复杂度O(n)

```class Solution {
public static int getMinKthByBFPRT(int[] arr,int k) {
int[] copyArr = new int[arr.length];
copyArr = copyArray(arr);
return bfprt(copyArr,0,copyArr.length - 1,k - 1);
}
public static int[] copyArray(int[] arr) {
int[] tmp = new int[arr.length];
for(int i = 0;i != arr.length;i++)
tmp[i] = arr[i];
return tmp;
}
public static int bfprt(int[] arr,int begin,int end,int i) {//begin到end范围内求第i小的数
if(begin == end)
return arr[begin];
int pivot = medianOfMedians(arr,begin,end);//中位数作为划分值
int[] pivotRange = partition(arr,begin,end,pivot);//进行划分，返回等于区域
if(i >= pivotRange[0] && i <= pivotRange[1])
return arr[i];
else if(i < pivotRange[0])
return bfprt(arr,begin,pivotRange[0] - 1,i);
else
return bfprt(arr,pivotRange[1] + 1,end,i);
}

public static int medianOfMedians(int[] arr,int begin,int end) {
int num = end - begin + 1;
int offset = num % 5 == 0 ? 0 : 1;
int[] mArr = new int[num / 5 + offset];
for(int i = 0; i < mArr.length;i++) {
int beginI = begin + i * 5;
int endI = beginI + 4;
mArr[i] = getMedian(arr,beginI,Math.min(end,endI));
}
return bfprt(mArr,0,mArr.length - 1,mArr.length / 2);
}

public static int getMedian(int[] arr,int begin,int end) {
Arrays.sort(arr,begin,end);
int sum = end + begin;
int mid = (sum / 2) + (sum % 2);
return arr[mid];
}

public static void insertSort(int[] arr,int begin,int end) {
for(int i = begin + 1;i != end + 1;i++) {
for(int j = i;j != begin;j--) {
if(arr[j - 1] > arr[j])
swap(arr,j - 1,j);
else
break;
}
}
}
public static int[] partition(int[] arr,int begin,int end,int pivotValue) {
int small = begin - 1;
int cur = begin;
int big = end + 1;
while(cur != big) {
if(arr[cur] < pivotValue)
swap(arr,++small,cur++);
else if(arr[cur] > pivotValue)
swap(arr,cur,--big);
else
cur++;
}
int[] range = new int[2];
range[0] = small + 1;
range[1] = big - 1;
return range;
}

public static void swap(int[] arr,int i,int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public int findKthLargest(int[] nums, int k) {
return getMinKthByBFPRT(nums,nums.length - k + 1);
}
}```

0 条评论

• ### CodeForces D.Powerful array(Div.1)

大意是是说，问区间[L,R]内的的一个值，这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle，...

• ### BFPRT算法

首先将原数组分成5个一组，每组内进行排序，组间不排序，然后将每组的中位数取出再次进行上述操作，直到最后只能分成一组了，然后取出中位数，将这个中位数当作标尺进行...

• ### ECJTUACM16 Winter vacation training #5 题解&源码

A-------------------------------------------------------------------------------...

• ### loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)

我们可以把图行列拆开，同时对于行/列拆成很多个联通块，然后考虑每个点所在的行联通块/列联通块的贡献。

• ### CodeForces D.Powerful array(Div.1)

大意是是说，问区间[L,R]内的的一个值，这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle，...

• ### 13:大整数的因子

13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9，现给出长度最大为30位...

• ### BFPRT算法

首先将原数组分成5个一组，每组内进行排序，组间不排序，然后将每组的中位数取出再次进行上述操作，直到最后只能分成一组了，然后取出中位数，将这个中位数当作标尺进行...

• ### 《linux c 编程一站式学习》课后部分习题解答

1、假设变量x和n是两个正整数，我们知道x/n这个表达式的结果要取Floor，例如x是17，n是4，则结果是4。如果希望结果取Ceiling应该怎么写表达式呢？...

• ### 浙大版《C语言程序设计（第3版）》题目集 习题10-6 递归求Fabonacci数列

f(n)=f(n−2)+f(n−1) (n≥2)，其中f(0)=0，f(1)=1。