这道题目是用排序做不出来的。很没含量。
然后看了下 quick selection 算法。打算明天自己重写下。
待补充。
今天和女朋友算是大吵了架。然后各种事吧。
继续把。
这道题目。我目前用了三种做法。正好复习了下快速排序，堆排序这些比起基础排序稍微更复杂些的算法。然后有了更多的认识。
最简单的做法。先排序。然后直接找。
/* quick sort and get it
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0)
return -1;
Arrays.sort(nums);
return nums[nums.length - k];
}
*/
这种做法没有任何技术含量。不解释了。
第二种做法。 快速选择， quick select
为什么会有这么一种做法。
快排的时候，我们会使用一个函数，partition,找到这段数组的区分点，然后再次使用递归分别对两段子sub array 使用快速排序。
但是对于查找。如果我们确定我们要找的数字，在一段中，我们根本不在乎另外一段。所以根本不需要对他进行排序。直接对我们确定的那一段进行排序就行了。
这就是快速选择的基本思想。
然后算法导论里面讲的更复杂。因为现在我的解法，是有最坏结果的。也就是快速排序最坏结果的情况，对于快速选择，同样也是最坏的。算法导论里面，讲的貌似就是怎么把最坏情况的复杂度，也降到线性。在这里我就不做研究了。就像我对快速排序的做法，也是沿袭了普林斯顿算法的习惯，一开始就 shuffle sort 一下。
但是。。。
这个快速选择的复杂度是线性的，而shuffle sort是nlogn. 所以快速选择里不能使用这个思想。然后网上的建议，就是找他们的中位数，然后以他作为 Pivot。
应该是可以的。但是我还是按照老方法做的。
代码如下：
/** quick select and get it */
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0)
return -1;
return quickSelect(nums, nums.length - k + 1, 0, nums.length - 1);
}
private int quickSelect(int[] nums, int k, int begin, int end) {
if (begin > end)
return -1;
else if (begin == end)
return nums[begin];
int j = partition(nums, begin, end);
if (k < (j - begin + 1))
return quickSelect(nums, k, begin, j - 1);
else if (k > (j - begin + 1))
return quickSelect(nums, k - (j - begin + 1), j + 1, end);
else
return nums[j];
}
private int partition(int[] nums, int begin, int end) {
int v = nums[begin];
int i = begin;
int j = end + 1;
while (i <= j) {
while (nums[++i] <= v) {
if (i >= end)
break;
}
while (nums[--j] > v) {
if (j <= 0)
break;
}
if (i >= j) // take care, here must be >=
break;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
nums[begin] = nums[j];
nums[j] = v;
return j;
}
然后快排的注意点。
if (i >= j)
这里必须是 >= !!!!!!
否则会有潜在的bug
什么时候会出现 i >= j
快排中，i 指的元素都是 > v
j 指的元素都是 <= v
所以大多数情况下，当i在某个元素停下。此时这个元素 >= v
然后j开始往后退，碰到这个元素的时候，不会停下，继续往后退一格。
然后停下。
所以一般最后的结局都是 i > j 。那么我们为什么需要 i >= j呢
似乎 i 不会有机会 = j
当一个子数列，所有的元素都小于v 时
i = end
然后j开始跑。 --j, 此时 j = end
然后发现是 <= v 的，于是立刻停下。
此时 i == j
然后如果没有 i >= j 中的等于。
循环不会结束，继续执行。
然后 ++i 会造成数组越界。
所以 >= 是必须的！
第三种做法。堆排序。
为什么快排的时间消耗的多。因为，很多东西我不需要去排。
所以，堆排序，类似于一种在动态的过程中不断进行排序，贪婪思想的排序算法，最适合这种查找。
我需要找到k大，那么，我只要把堆的头移出去k次。第k次，一定是第k大的。
所以之后的那些排序时间我就不用花了。而且根本不在乎最好最坏复杂度。
下面稍微说一下堆排序。
我之前做了总结，但是因为事情太多，没有放上来。
堆排序是神级排序。
他的复杂度一直是 nlogn, 最坏情况下也是如此。
快排呢，最坏情况时 o n^2. 也就是，当数组已经逆序排好了的时候。复杂度会很糟糕。
所以这一点，堆排序完爆快排。
归并排序呢，最好最坏也都是 o nlogn. 但是，归并排序不是in place，需要额外申请内存。而堆排序是 in place 的。
你看我的代码里好像有复制数组的地方。
因为数组的index都是从0开始的，如果这样使用堆排序，代码写起来会烦一些。如果直接从1开始，会方便很多。
儿子一定是 2 * i, 2 × i + 1
父亲一定是 i / 2
所以我这个相当于简化版堆排序。但是从0开始的，完全可以写出来。
所以内存使用方面，堆排序又完爆归并排序，merge sort.
PS： 其实归并排序可以做成 in place 的，这是我老师告诉我的。。太夸张了。但是做成in place 之后，代码首先会复杂很多，其次会有很多逻辑判断，所以最终导致速度不如以前了，也许节约了内存，但是已经失去了 merge sort 本身的意义。
然后还有个惊天消息。 oracle java 的 Arrays.sort() 这个方法其实是错误的。
也就是说，这个官方API代码是有bug的。但是为什么我们平时使用完全没问题呢？
因为这个bug几乎不可能发生。老师说，需要构造一个一百多万位，特殊构造的数组，才可以暴露这个bug。
继续。
那么，堆排序在各个方面，领先于，快排，归并排序。我们很少用呢？
因为 cache performance.
想象一下啊。堆排序，经常是 i 与 i * 2这样一个层级进行比较。如果 i 很大，两者之间的差距是很大的。
而且每次swim，会将许多距离很远的数字进行比较。很可能有些数字并没有放进cache中。所以CPU得特地再把那些数字从内存中取出来放进cache
所以，堆排序的cache performace 很糟糕。
像快排，都是元素和一个 pivot value 在比，不需要和远处的元素比。cache performance 目测不会差。
归并排序，是两个数组的相近位置进行比较，感觉也不会差。
所以，老师说，堆排序这方面的缺陷影响太多，所以退出了主流排序的舞台。
对于cache performace 这个论断，我其实并没有真正理解，只是自己感觉了下对的。
有机会要去看下CSAPP的cache部分。
差不多就说完了。
忘记上代码了：
/** heap sort and get it */
private int N = 0;
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0)
return -1;
N = nums.length;
int[] aux = new int[N + 1];
for (int i = 1; i < N + 1; i++)
aux[i] = nums[i - 1];
for (int i = N / 2; i >= 1; i--)
swim(aux, i);
for (int i = 1; i < k; i++)
bottom(aux);
return bottom(aux);
}
private void swim(int[] aux, int index) {
int i = index * 2;
while (i <= N) {
if (i + 1 <= N && aux[i + 1] > aux[i])
i = i + 1;
if (aux[index] < aux[i]) {
int temp = aux[index];
aux[index] = aux[i];
aux[i] = temp;
index = i;
i = 2 * i;
}
else
break;
}
}
private int bottom(int[] aux) {
int ret = aux[1];
aux[1] = aux[N];
aux[N] = ret;
N--;
int i = 1;
int j = 2 * i;
while (j <= N) {
if (j + 1 <= N && aux[j + 1] > aux[j])
j = j + 1;
if (aux[i] < aux[j]) {
int temp = aux[i];
aux[i] = aux[j];
aux[j] = temp;
i = j;
j = 2 * i;
}
else
break;
}
return ret;
}
**
总结： 快速选择， 堆排序
**
Anyway, Good luck,Richardo!
My code:
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return 0;
}
shuffle(nums);
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int pivot = begin;
int i = begin + 1;
int j = end;
while (i <= j) {
while (i <= end && nums[i] < nums[pivot]) {
i++;
}
while (j > pivot && nums[j] > nums[pivot]) {
j--;
}
if (i > j) {
break;
}
else {
int temp = nums[i];
nums[i] = nums[j];
nums[j]= temp;
i++;
j--;
}
}
int temp = nums[pivot];
nums[pivot] = nums[j];
nums[j] = temp;
if (nums.length - j == k) {
return nums[j];
}
else if (nums.length - j > k) {
begin = j + 1;
}
else {
end = j - 1;
}
}
return -1;
}
private void shuffle(int[] nums) {
Random r = new Random();
for (int i = 1; i < nums.length; i++) {
int ri = r.nextInt(i + 1);
int temp = nums[ri];
nums[ri] = nums[i];
nums[i] = temp;
}
}
}
reference:
https://discuss.leetcode.com/topic/14597/solution-explained
我一开始自己写了一个 quick select,但是并没有加入shuffle
所以速度很慢。
后来看了提示，可以加 shuffle,复杂度是O(n)
然后速度一下子提升了上去。
还有一种复杂的算法教你如果选择pivot导致最坏情况下，复杂度仍然是O(n),这里就不看了。
这道题目还可以用最小堆。
尤其当输入是流时，quick select 并不能很好的发挥作用，而Min-heap
的时间复杂度是 nlogk,空间复杂度是 k
可以很好的解决流的问题。
Anyway, Good luck, Richardo! -- 09/04/2016
My code:
public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < nums.length; i++) {
if (pq.size() < k) {
pq.offer(nums[i]);
}
else {
if (pq.peek() >= nums[i]) {
continue;
}
else {
pq.poll();
pq.offer(nums[i]);
}
}
}
return pq.peek();
}
}
time complexity: O(n log k)
K-Min Heap
Quick Select:
import java.util.Random;
public class Solution {
public int findKthLargest(int[] nums, int k) {
shuffle(nums);
return quickSelect(nums, nums.length - k);
}
private int quickSelect(int[] nums, int k) { // k is index
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int j = partition(nums, lo, hi);
if (j == k) {
return nums[j];
}
else if (j < k) {
lo = j + 1;
}
else {
hi = j - 1;
}
}
return -1;
}
private int partition(int[] nums, int lo, int hi) {
int pivot = lo;
lo += 1;
while (lo <= hi) {
while (lo < nums.length && nums[lo] < nums[pivot]) {
lo++;
}
while (hi >= 0 && nums[hi] > nums[pivot]) {
hi--;
}
if (lo >= hi) {
break;
}
int temp = nums[lo];
nums[lo] = nums[hi];
nums[hi] = temp;
lo++;
hi--;
}
int temp = nums[pivot];
nums[pivot] = nums[hi];
nums[hi] = temp;
return hi;
}
private void shuffle(int[] nums) {
Random r = new Random();
for (int i = 1; i < nums.length; i++) {
int index = r.nextInt(i + 1);
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
}
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[]{3,2,1,5,6,4};
int ret = test.findKthLargest(nums, 2);
System.out.println(ret);
}
}
先转换成找最小的k (index), 然后再 quick select.
Anyway, Good luck, Richardo! -- 09/24/2016
