這是一道很經(jīng)典的題目孵延，我在看別人面經(jīng)的時(shí)候不止一次看到了這道題惶凝，因此我們還是很有必要去好好分析一下這道題的。
本題可以用快速排序的partition來解犬钢，或者用堆排序構(gòu)建最小堆來解苍鲜。

一、題目

在未排序的數(shù)組中找到第 k 個(gè)最大的元素玷犹。請注意混滔，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素歹颓。

示例1:

輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

示例2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4

說明:

你可以假設(shè) k 總是有效的坯屿，且 1 ≤ k ≤ 數(shù)組的長度。

二巍扛、分析

我們可以先對(duì)整體數(shù)據(jù)排序愿伴，然后找出來第k個(gè)數(shù)，排序方法我們可以用快速排序电湘、堆排序隔节、歸并排序等鹅经，這樣平均時(shí)間復(fù)雜度是n*log(n)。

2.1 使用最小堆來解

既然讓我們找出第k個(gè)最大的數(shù)怎诫，那么我們是不是可以維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)瘾晃，這個(gè)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)k個(gè)值，并且是已排序的呢幻妓？我們就想到了堆蹦误。最小堆的父節(jié)點(diǎn)都不大于兩個(gè)子節(jié)點(diǎn)。因此我們可以構(gòu)建一個(gè)最小堆肉津，堆的大小是k强胰；遍歷數(shù)組中的其他元素，如果大于堆頂元素妹沙，則替換偶洋，重新構(gòu)造最小堆；直到所有元素遍歷完距糖，我們得到了這樣一個(gè)最小堆：堆中元素比數(shù)組中其他元素都大玄窝。那么，堆頂元素就是我們要找的第k個(gè)最大的數(shù)字悍引。
時(shí)間復(fù)雜度分析：
最壞情況：數(shù)組已經(jīng)是升序排列了恩脂，時(shí)間復(fù)雜度是n*log(k)
最好情況：數(shù)組已經(jīng)降序排列了，時(shí)間復(fù)雜度是n
平均時(shí)間復(fù)雜度：n

2.2 使用partition

我們回顧一下快速排序的思想趣斤，每次講一個(gè)數(shù)字放到他適合的位置（他小于等于他前面的數(shù)組俩块，并且他大于等于他后面的數(shù)組）。
如果這個(gè)數(shù)字適合的位置恰好是k呢浓领？那么我們不就得到第k大的數(shù)字了嗎玉凯？我們既不需要為他前面的數(shù)字排序，也不需要為他后面的數(shù)字排序镊逝，我們只需要得到第k大的數(shù)字就行壮啊。
時(shí)間復(fù)雜度分析：
最壞情況：數(shù)字是升序排列的，并且我們每次partition選的數(shù)字都是第一個(gè)數(shù)字撑蒜，時(shí)間復(fù)雜度是n*log(n)歹啼。
平均時(shí)間復(fù)雜度：n

三、代碼

java 構(gòu)建最小堆

int[] src = null;
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length)
            return Integer.MAX_VALUE;
        src = nums;
        //構(gòu)造最小堆
        for (int i = (k - 2) / 2; i >= 0; i--) {
            adjustHeap(i, k - 1);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > nums[0]) {
                swap(i, 0);
                adjustHeap(0, k-1);
            }
        }
        return nums[0];
    }
    
    //構(gòu)建最小堆
    private void adjustHeap(int start, int end) {
        int temp = src[start];
        int j = start * 2 + 1;
        for (j = start * 2 + 1; j <= end; j = j * 2 + 1) {
            if (j < end && src[j] > src[j + 1]) {
                j++;
            }
            if (temp > src[j]) {
                src[start] = src[j];
                start = j;
            } else {
                break;
            }
        }
        src[start] = temp;
    }
    
    private void swap(int i, int j) {
        int temp = src[i];
        src[i] = src[j];
        src[j] = temp;
    }

java partition

    int result = 0;
    int[] src = null;
    int target = 0;
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length)
            return result;
        result = nums[0];
        src = nums;
        target = k-1;
        partition(0,src.length - 1);
        return result;
    }
    
    private void partition (int start, int end) {
        if (start > end)
            return;
        int temp = src[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && src[j] <= temp) {
                j--;
            }
            if (i < j) {
                src[i] = src[j];
                i++;
            }
            while (i < j && src[i] >= temp) {
                i++;
            }
            if (i < j) {
                src[j] = src[i];
                j--;
            }
        }
        src[i] = temp;
        if (i == target) {
            result = src[i];
            return;
        } else {
            if (i > target) {
                partition(start, i-1);   
            } else {
                partition(i+1, end);                
            }
        }
    }