隨機選擇

習題預習

1. 在一個包含n個元素的未排序數組中找到第k個最小元素。
2. 給定一個含有n個元素的未排序數組，找到其中第k個最大元素。
3. 在一個包含n個元素的未排序數組中找到中位數。
4. 找到一個數組中的第i個元素，使得它左邊的元素都比它小，右邊的元素都比它大。
5. 找到一個數組中最接近中位數的元素。

說明知識

Randomized Selection是一種選擇性能比QuickSort還要優異的算法，可以在O(n)的時間複雜度內選擇一個陣列中第k小（大）的元素。

該算法的基本思想是選擇一個隨機數作為pivot（基準點），將陣列分為兩個部分，一部分比pivot小，一部分比pivot大。然後判斷第k小（大）的元素在哪個部分中，進行分治遞歸操作，直到找到第k小（大）的元素為止。

以下是一個說明Randomized Selection的Python代碼範例：

import random

def randomized_selection(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x > pivot]
    mid = [x for x in arr if x == pivot]
    if k <= len(left):
        return randomized_selection(left, k)
    elif k > len(left) + len(mid):
        return randomized_selection(right, k-len(left)-len(mid))
    else:
        return mid[0]

在這個例子中，我們首先選擇隨機pivot，然後將陣列分成三部分：比pivot小的元素、比pivot大的元素、和等於pivot的元素。接著，我們判斷第k小（大）的元素在哪個部分中，進行分治遞歸操作。如果k小於等於左邊部分的元素個數，那麼第k小的元素必然在左邊，我們就遞歸對左邊的陣列進行操作。如果k大於左邊部分的元素個數加上等於pivot的元素個數，那麼第k小的元素必然在右邊，我們遞歸對右邊的陣列進行操作。如果k介於左邊部分的元素和等於pivot的元素的個數之間，那麼第k小的元素就是pivot本身。

以上就是Randomized Selection的基本概念和使用範例。該算法通常比其他排序算法效率更高，因為它採用隨機pivot，可以避免最壞情況下的時間複雜度。

彙總重點

1. Randomized Selection是一種利用隨機化算法來找到數組中第k小元素的算法。

2. 該算法的關鍵是在每一次遍歷數組時隨機選擇一個pivot元素，把小於pivot的元素放到pivot左邊，大於pivot的元素放到pivot右邊，然後根據pivot的位置決定接下來的操作。

3. 如果pivot的位置恰好是k-1，那麼第k小元素就是pivot；如果pivot的位置小於k-1，則在右側子數組中遞歸查找第k-pivot位置的元素；如果pivot的位置大於k-1，則在左側子數組中遞歸查找第k個元素。

4. 該算法的時間複雜度為平均情況下O(n)，最壞情況下O(n^2)。

5. 為了避免最壞情況的發生，可以在每次遞歸時隨機選擇pivot，而不是固定選擇數組的第一個元素或最後一個元素。

6. Randomized Selection常用於解決第k小元素或第k大元素的問題，例如找到中位數或top k問題。

7. 總之，Randomized Selection是一種簡單、高效的算法，適用於快速查找數組中第k小元素。

知識測驗

1. 給定一個整數數組和一個整數k，找出數組中第k小的元素。

答案：使用Randomized Selection算法，平均時間複雜度為O(n)。

2. 在給定的整數數組中找到第二大的數。

答案：實現Randomized Selection，將每個元素與第一個標兵進行比較，然後將數組切分到第二大的數為止。

3. 給定一個未排序的數列，找出其中的中位數。

答案：使用Randomized Selection算法，從中選擇一個標兵元素，然後比較將數組切分為左右兩個子數組。

4. 給定一個數列，找到其中第k個重複出現的元素。

答案：使用Randomized Selection算法找到第k小元素，然後在剩餘的數組中進行線性查找。

5. 給定一個整數數組，找到最大的k個元素。

答案：使用Randomized Selection算法，將數組切分為左右兩部分，遞歸查找前k大的元素，然後歸並兩個子數組。