這道題目是用排序做不出來的。很沒含量。
然后看了下 quick selection 算法。打算明天自己重寫下。
待補充。

今天和女朋友算是大吵了架。然后各種事吧。

繼續(xù)把。

這道題目。我目前用了三種做法。正好復習了下快速排序，堆排序這些比起基礎(chǔ)排序稍微更復雜些的算法。然后有了更多的認識。

最簡單的做法。先排序。然后直接找。

/* 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];
    }
    */

這種做法沒有任何技術(shù)含量。不解釋了。

第二種做法。 快速選擇， quick select
為什么會有這么一種做法。
快排的時候，我們會使用一個函數(shù)，partition,找到這段數(shù)組的區(qū)分點，然后再次使用遞歸分別對兩段子sub array 使用快速排序。
但是對于查找。如果我們確定我們要找的數(shù)字，在一段中，我們根本不在乎另外一段。所以根本不需要對他進行排序。直接對我們確定的那一段進行排序就行了。
這就是快速選擇的基本思想。
然后算法導論里面講的更復雜。因為現(xiàn)在我的解法，是有最壞結(jié)果的。也就是快速排序最壞結(jié)果的情況，對于快速選擇，同樣也是最壞的。算法導論里面，講的貌似就是怎么把最壞情況的復雜度，也降到線性。在這里我就不做研究了。就像我對快速排序的做法，也是沿襲了普林斯頓算法的習慣，一開始就 shuffle sort 一下。
但是。。。
這個快速選擇的復雜度是線性的，而shuffle sort是nlogn. 所以快速選擇里不能使用這個思想。然后網(wǎng)上的建議，就是找他們的中位數(shù)，然后以他作為 Pivot。
應(yīng)該是可以的。但是我還是按照老方法做的。
代碼如下：

    /** 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
什么時候會出現(xiàn) i >= j
快排中，i 指的元素都是 > v
j 指的元素都是 <= v
所以大多數(shù)情況下，當i在某個元素停下。此時這個元素 >= v
然后j開始往后退，碰到這個元素的時候，不會停下，繼續(xù)往后退一格。
然后停下。
所以一般最后的結(jié)局都是 i > j 。那么我們?yōu)槭裁葱枰?i >= j呢
似乎 i 不會有機會 = j
當一個子數(shù)列，所有的元素都小于v 時
i = end
然后j開始跑。 --j, 此時 j = end
然后發(fā)現(xiàn)是 <= v 的，于是立刻停下。
此時 i == j
然后如果沒有 i >= j 中的等于。
循環(huán)不會結(jié)束，繼續(xù)執(zhí)行。
然后 ++i 會造成數(shù)組越界。
所以 >= 是必須的！

第三種做法。堆排序。
為什么快排的時間消耗的多。因為，很多東西我不需要去排。
所以，堆排序，類似于一種在動態(tài)的過程中不斷進行排序，貪婪思想的排序算法，最適合這種查找。
我需要找到k大，那么，我只要把堆的頭移出去k次。第k次，一定是第k大的。
所以之后的那些排序時間我就不用花了。而且根本不在乎最好最壞復雜度。
下面稍微說一下堆排序。
我之前做了總結(jié)，但是因為事情太多，沒有放上來。
堆排序是神級排序。
他的復雜度一直是 nlogn, 最壞情況下也是如此。
快排呢，最壞情況時 o n^2. 也就是，當數(shù)組已經(jīng)逆序排好了的時候。復雜度會很糟糕。
所以這一點，堆排序完爆快排。
歸并排序呢，最好最壞也都是 o nlogn. 但是，歸并排序不是in place，需要額外申請內(nèi)存。而堆排序是 in place 的。
你看我的代碼里好像有復制數(shù)組的地方。
因為數(shù)組的index都是從0開始的，如果這樣使用堆排序，代碼寫起來會煩一些。如果直接從1開始，會方便很多。
兒子一定是 2 * i, 2 × i + 1
父親一定是 i / 2
所以我這個相當于簡化版堆排序。但是從0開始的，完全可以寫出來。
所以內(nèi)存使用方面，堆排序又完爆歸并排序，merge sort.
PS： 其實歸并排序可以做成 in place 的，這是我老師告訴我的。。太夸張了。但是做成in place 之后，代碼首先會復雜很多，其次會有很多邏輯判斷，所以最終導致速度不如以前了，也許節(jié)約了內(nèi)存，但是已經(jīng)失去了 merge sort 本身的意義。
然后還有個驚天消息。 oracle java 的 Arrays.sort() 這個方法其實是錯誤的。
也就是說，這個官方API代碼是有bug的。但是為什么我們平時使用完全沒問題呢？
因為這個bug幾乎不可能發(fā)生。老師說，需要構(gòu)造一個一百多萬位，特殊構(gòu)造的數(shù)組，才可以暴露這個bug。

繼續(xù)。
那么，堆排序在各個方面，領(lǐng)先于，快排，歸并排序。我們很少用呢？
因為 cache performance.
想象一下啊。堆排序，經(jīng)常是 i 與 i * 2這樣一個層級進行比較。如果 i 很大，兩者之間的差距是很大的。
而且每次swim，會將許多距離很遠的數(shù)字進行比較。很可能有些數(shù)字并沒有放進cache中。所以CPU得特地再把那些數(shù)字從內(nèi)存中取出來放進cache
所以，堆排序的cache performace 很糟糕。
像快排，都是元素和一個 pivot value 在比，不需要和遠處的元素比。cache performance 目測不會差。
歸并排序，是兩個數(shù)組的相近位置進行比較，感覺也不會差。
所以，老師說，堆排序這方面的缺陷影響太多，所以退出了主流排序的舞臺。
對于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;
    }

**
總結(jié)： 快速選擇， 堆排序
**

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 并不能很好的發(fā)揮作用，而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);
    }
}

先轉(zhuǎn)換成找最小的k (index), 然后再 quick select.

Anyway, Good luck, Richardo! -- 09/24/2016