查詢陣列中第K大的元素

要查詢一個陣列中的第 K 大元素，有多種方法可以實現，其中常用的方法是使用分治演演算法或快速選擇演演算法，這兩種方法的時間複雜度到時候O(n)。

快速選擇演演算法範例：

package main

import "fmt"

func findKthLargest(nums []int, k int) int {
    return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(nums []int, left, right, k int) int {
    if left == right {
        return nums[left]
    }
    pivotIndex := partition(nums, left, right)
    if k == pivotIndex {
        return nums[k]
    } else if k < pivotIndex {
        return quickSelect(nums, left, pivotIndex-1, k)
    } else {
        return quickSelect(nums, pivotIndex+1, right, k)
    }
}

func partition(nums []int, left, right int) int {
    pivot := nums[right]
    i := left
    for j := left; j < right; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    nums[i], nums[right] = nums[right], nums[i]
    return i
}

func main() {
    nums := []int{3, 2, 1, 5, 6, 4}
    k := 2
    result := findKthLargest(nums, k)
    fmt.Printf("The %d-th largest element is: %d\n", k, result)
}

上述程式碼使用快速選擇演演算法來查詢第 K 大的元素，其中 quickSelect 函數遞迴地在左半部分或右半部分查詢，直到找到第 K 大的元素。partition 函數用於對陣列進行分割區操作，將小於 pivot 值的元素移到左邊，大於 pivot 值的元素移到右邊。

這種方法的平均時間複雜度為 O(n)，其中 n 是陣列的長度。最壞情況下的時間複雜度為 O(n^2)，但快速選擇演演算法通常在平均情況下表現良好。這個演演算法是一種不需要額外引入空間消耗的高效查詢方法。

注意，也可以考慮使用標準庫中的排序函數，然後直接存取第 K 大的元素，但這會引入 O(nlogn) 的排序時間複雜度，因此不如快速選擇演演算法高效。

分治演演算法範例

使用分治演演算法查詢陣列中第 K 大的元素是一種高效的方法，其時間複雜度為 O(n)。下面是使用分治演演算法實現的查詢第 K 大元素的過程：

分解（Divide）：將陣列分為若干個子陣列，每個子陣列包含一組元素。可以使用任何方法來劃分陣列，例如隨機選擇一個元素作為樞紐元素（pivot），然後將陣列中小於樞紐元素的元素放在左側，大於樞紐元素的元素放在右側。這個過程類似於快速排序中的分割區操作。
選擇子陣列（Select Subarray）：根據分解步驟中得到的子陣列和樞紐元素的位置，確定要繼續查詢的子陣列。如果 K 大元素的位置在樞紐元素的右側，那麼在右側的子陣列中繼續查詢；如果在左側，那麼在左側的子陣列中查詢。
遞迴（Recursion）：遞迴地在所選子陣列中查詢第 K 大元素。這個過程會反覆進行，直到找到第 K 大元素或確定它在左側或右側的子陣列中。
合併（Combine）：合併步驟通常不需要執行，因為在遞迴的過程中，只需繼續查詢左側或右側的子陣列中的第 K 大元素。
基本情況（Base Case）：遞迴的終止條件通常是當子陣列只包含一個元素時，即找到了第 K 大元素。

下面是一個範例的 Go 程式碼，實現了查詢陣列中第 K 大元素的分治演演算法：

package main

import "fmt"

func findKthLargest(nums []int, k int) int {
    if len(nums) == 1 {
        return nums[0]
    }

    pivotIndex := partition(nums)
    rank := pivotIndex + 1

    if rank == k {
        return nums[pivotIndex]
    } else if rank > k {
        return findKthLargest(nums[:pivotIndex], k)
    } else {
        return findKthLargest(nums[pivotIndex+1:], k-rank)
    }
}

func partition(nums []int) int {
    pivotIndex := len(nums) - 1
    pivot := nums[pivotIndex]
    i := 0

    for j := 0; j < pivotIndex; j++ {
        if nums[j] > pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }

    nums[i], nums[pivotIndex] = nums[pivotIndex], nums[i]
    return i
}

func main() {
    arr := []int{3, 2, 1, 5, 6, 4}
    k := 2
    result := findKthLargest(arr, k)
    fmt.Printf("The %d-th largest element is: %d\n", k, result)
}

這個範例中，findKthLargest 函數使用了分治演演算法，通過遞迴地在子陣列中查詢第 K 大元素，直到找到或確定其在左側或右側的子陣列中。partition 函數用於將陣列分為左側大於樞紐元素和右側小於樞紐元素的兩部分。

這個演演算法的時間複雜度是 O(n)，其中 n 是陣列的長度。這是因為在每次遞迴中，都會將陣列一分為二，從而快速縮小問題規模。這使得分治演演算法成為一種高效的查詢第 K 大元素的方法。

氣泡排序範例

氣泡排序是一種排序演演算法，通常不是用來查詢第 K 大的元素的最佳選擇，因為它的時間複雜度較高。然而，你可以結合氣泡排序的思想來查詢陣列中第 K 大的元素。具體方法是對陣列進行 K 次氣泡排序，每次氣泡排序將當前最大的元素移動到陣列的末尾，然後查詢第 K 大的元素。下面是一個範例實現：

package main

import "fmt"

func findKthLargest(nums []int, k int) int {
    if k < 1 || k > len(nums) {
        return -1 // 無效的 K
    }

    for i := 0; i < k; i++ {
        for j := 0; j < len(nums)-i-1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j] // 氣泡排序
            }
        }
    }

    // 第 K 大的元素位於陣列倒數第 K 個位置
    return nums[len(nums)-k]
}

func main() {
    arr := []int{3, 2, 1, 5, 6, 4}
    k := 2
    result := findKthLargest(arr, k)
    fmt.Printf("The %d-th largest element is: %d\n", k, result)
}

在上述範例中，findKthLargest 函數執行 K 次氣泡排序，每次將當前最大的元素冒泡到陣列的末尾。最後，第 K 大的元素位於陣列倒數第 K 個位置。這個演演算法的時間複雜度是 O(K*n)，其中 n 是陣列的長度。雖然不是最高效的演演算法，但對於小 K 值或小陣列來說，是可行的方法。如果 K 較大或陣列很大，建議使用其他更高效的演演算法。

宣告：本作品採用署名-非商業性使用-相同方式共用 4.0 國際 (CC BY-NC-SA 4.0)進行許可，使用時請註明出處。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 戀水無意