LeetCode 215. Kth Largest Element in an Array分析

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 ≤ k ≤ array's length. 在数组中找到第k大的元素 注意事项 你可以交换数组中的元素的位置 样例 给出数组 [9,3,2,4,8]，第三大的元素是 4 给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推

分析

1直接排序

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

** O(N lg N) running time + O(1) memory **

2 利用堆

```public int findKthLargest(int[] nums, int k) {

final PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
pq.offer(val);

if(pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}```

** O(N lg K) running time + O(K) memory **

3 快排思想

```public int findKthLargest(int[] nums, int k) {

k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}

private int partition(int[] a, int lo, int hi) {

int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && less(a[++i], a[lo]));
while(j > lo && less(a[lo], a[--j]));
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}

private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

private boolean less(int v, int w) {
return v < w;
}```

4改进快排

```public class Solution {
public int findKthLargest(int[] nums, int k) {

shuffle(nums);
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}

private void shuffle(int a[]) {

final Random random = new Random();
for(int ind = 1; ind < a.length; ind++) {
final int r = random.nextInt(ind + 1);
exch(a, ind, r);
}
}

private int partition(int[] a, int lo, int hi) {

int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && less(a[++i], a[lo]));
while(j > lo && less(a[lo], a[--j]));
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}

private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

private boolean less(int v, int w) {
return v < w;
}
}```

0 条评论

• LintCode整数排序题目分析解答选择排序插入排序小结

Given an integer array, sort it in ascending order. Use selection sort, bubble s...

• [编程题] 赶去公司代码

终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，...

• LeetCode 75. Sort Colors题目分析

给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0，1 和 2 分别代...

• P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输...

• 蓝桥杯--算法入门级题目及答案解析

写在最前面： 本文中会出现大量的请查阅.请自学什么的，不是我不讲，本文是面向算法初学者和蓝桥杯的文章，如果真的想看进阶算法的也不会来看这些题目，所以不要介意，...

• LeetCode第五天

leetcode 第五天 2018年1月6日 22.(566) Reshape the Matrix ? ? JAVA class Solution { ...

• 算法原理系列：木桶排序

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• 高仿京东金融的数值滚动尺

以前博客讲的大部分都是静态的自定义View的编写,其实无非就是“画画”画出一个好看的效果,而这篇博客写的是写一个动态的自定义控价,这里不仅需要"画",还要各种事...