LintCode 題解丨阿裡巴巴面試題：第k大元素

在數組中找到第 k 大的元素。(你可以交換數組中的元素的位置)

線上評測位址：

​

https://www.lintcode.com/problem/kth-largest-element/?utm_source=sc-tianchi-sz0826

樣例 1：

輸入：

n = 1, nums = [1,3,4,2]

輸出：

4

樣例 2：

n = 3, nums = [9,3,2,4,8]

【題解】

算法：快速選擇算法

最容易想到的就是直接排序，傳回第k大的值。時間複雜度是O(nlogn)，這裡提供O(n)的解法。

這題其實是快速排序算法的變體，在九章算法班中也有詳細講解。通過快速排序算法的partition步驟，可以将小于pivot的值劃分到pivot左邊，大于pivot的值劃分到pivot右邊，是以可以直接得到pivot的rank。進而縮小範圍繼續找第k大的值。

partition步驟：

令left = start，right = end，pivot = nums[left]。

當nums[left] < pivot時，left指針向右移動。

當nums[right] > pivot時，right指針向左移動。

交換兩個位置的值，right指針左移，left指針右移。

直到兩指針相遇，否則回到第2步。

每次partition後根據pivot的位置，尋找下一個搜尋的範圍。

複雜度分析

設數組長度為n

時間複雜度O(n)

對一個數組進行partition的時間複雜度為O(n)。

分治，選擇一邊繼續進行partition。

是以總的複雜度為T(n) = T(n / 2) + O(n)，總時間複雜度依然為O(n)。

空間複雜度O(1)

隻需要快速選擇遊标的O(1)額外空間。

public class Solution {

/**
 * @param n: An integer
 * @param nums: An array
 * @return: the Kth largest element
 */
public int kthLargestElement(int k, int[] nums) {
    int n = nums.length;
    // 為了友善編寫代碼，這裡将第 k 大轉換成第 k 小問題。
    k = n - k;
    return partition(nums, 0, n - 1, k);
}
public int partition(int[] nums, int start, int end, int k) {
    int left = start, right = end;
    int pivot = nums[left];
    
    while (left <= right) {
        while (left <= right && nums[left] < pivot) {
            left++;
        }
        while (left <= right && nums[right] > pivot) {
            right--;
        }
        if (left <= right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
    
    // 如果第 k 小在右側，搜尋右邊的範圍，否則搜尋左側。
    if (k <= right) {
        return partition(nums, start, right, k);
    }
    if (k >= left) {
        return partition(nums, left, end, k);
    }
    return nums[k];
}
public void swap(int[] nums, int x, int y) {
    int temp = nums[x];
    nums[x] = nums[y];
    nums[y] = temp;
}           

}

更多題解參見九章算法官網：

https://www.jiuzhang.com/solution/kth-largest-element/?utm_source=sc-tianchi-sz0826