[[409182]]

1. 尋找第K大

題意

有一個(gè)無序整數(shù)數(shù)組，請(qǐng)你根據(jù)排序思路，找出數(shù)組中第K大的數(shù)。

給定一個(gè)整數(shù)數(shù)組a, 請(qǐng)返回第K (1<=K<=n) 大的數(shù)(包括重復(fù)的元素，不用去重)，保證答案存在。

示例

輸入 [3，2，1，5，6，4] , 2 
返回值 5 

2. 常規(guī)思路

先對(duì)無序數(shù)組進(jìn)行排序，然后對(duì)有序數(shù)組進(jìn)行查找。

至于選擇什么排序算法，有待確定。

先看一下，各種排序算法的復(fù)雜度以及穩(wěn)定性。

看完上面比較之后，可能你心中已經(jīng)有了自己的答案。

3. 解題思路

常規(guī)思路需要兩大步：

1. 先整體排序
2. 在有序中查找目標(biāo)值

那么，針對(duì)這道題，我們能不能在排序的過程中就確定目標(biāo)值呢?

思考一下快排的二分特性：

1. 先找出一個(gè)數(shù)值的位置，該數(shù)值的左側(cè)比自己小，右側(cè)比自己大(整個(gè)數(shù)組一分為二)
2. 再分別進(jìn)行左、右兩部分進(jìn)行步驟1的操作，直至整個(gè)數(shù)組有序。

這里需要知道的是，在快排中某個(gè)數(shù)值左側(cè)比自己小，右側(cè)比自己大。該數(shù)值的位置就是在最終有序數(shù)組中的位置，也就是說可以在查找中確定目標(biāo)位置。并且，在本題的處理過程中，平均情況下只處理1/2的數(shù)據(jù)量。

動(dòng)圖 - 快排算法

快排算法查找過程：

4. Go代碼實(shí)現(xiàn)

func findKLargest(arr []int, k int) int { 
    iflen(arr) == 0 || k > len(arr) { 
        return-1 
    } 
 
    var find func(k int, l, r int) int 
    find = func(k int, l, r int) int { 
        /* 
        // 對(duì)于正常的快排，需要下面的代碼 
        if l >= r { 
            return 
        } 
        // 然而這里不需要，在尋找第k大的數(shù)據(jù)時(shí) 一般是 l==r 
        */ 
        ll := l 
        rr := r 
        target := arr[l] 
 
        // 倒序(第K大使用)排列 是 target >= arr[r]  / target <= arr[l] 
        // 正序(第k小使用)排列 是 target <= arr[r]  / target >= arr[l] 
        for l < r { 
            for l < r && target >= arr[r] { 
                r-- 
            } 
            arr[l] = arr[r] 
 
            for l < r && target <= arr[l] { 
                l++ 
            } 
            arr[r] = arr[l] 
        } 
       
        arr[l] = target 
        // k在l的右側(cè) 
        // 為什么 下面無論是在左右側(cè)，第一個(gè)參數(shù)都是k呢？ 
        // 因?yàn)?，k指的是要找的數(shù)值的下標(biāo)位置(第k大就是下標(biāo)k-1) 
        // 無論在左右側(cè)，對(duì)于數(shù)組arr來說，其對(duì)應(yīng)的下標(biāo)都是固定的 
        // 并且 l/r 每次都會(huì)變動(dòng)，所以k這里是固定的 
        if k > l { 
            // 這里的  l+1, rr 也是數(shù)組的下標(biāo) 
            return find(k, l+1, rr) 
        }elseif k < l { 
            // k在l的左側(cè) 
            // 這里的  ll, l-1 也是數(shù)組的下標(biāo) 
            return find(k, ll, l-1) 
        } 
 
        // 此時(shí)目標(biāo)自位置l處的target，就是第k個(gè)大的數(shù)值 
        return target 
    } 
 
    // 第k大的數(shù)值，對(duì)應(yīng)排序之后就是，數(shù)組下標(biāo)k-1 
    finds := find(k-1, 0, len(arr)-1) 
 
    return finds 
} 

 求第K大，則對(duì)數(shù)組排序排列。

求第K小，則對(duì)數(shù)組正序排列。

無論如何，都是從頭開始找，這樣處理更簡(jiǎn)單。