給定一個(gè)不同整數(shù)的數(shù)組和一個(gè)整數(shù)，其中 小于數(shù)組大小，任務(wù)是找到數(shù)組中第 k 個(gè)最小的元素。

示例：

Snipaste_2026-02-03_20-53-16.png

請(qǐng)注意，解決這個(gè)問(wèn)題的方法有多種，詳見(jiàn)《未排序數(shù)組中的k個(gè)最小/最大元素》。這里討論的解決方案在實(shí)踐中效果最佳。

其理念是使用隨機(jī)樞軸選擇來(lái)劃分?jǐn)?shù)組，通過(guò)聚焦子數(shù)組（第k個(gè)元素必須所在）來(lái)減少搜索空間。

一步步的方法：

選擇隨機(jī)樞軸：隨機(jī)選擇一個(gè)元素作為樞軸。這有助于避免某些情況下的最壞情況（比如數(shù)組已經(jīng)排序）。
劃分：重新排列數(shù)組，使所有小于樞軸的元素位于左側(cè)，大于樞軸的元素在右側(cè)。
遞歸搜索：一旦樞軸定位，如果其索引等于 n 的比較，則它是第 K 大元素。如果沒(méi)有，則遞歸搜索相應(yīng)的劃分（左或右），其中 n。

// Java program to find K’th Smallest/
// Largest Element in Unsorted Array
import java.util.Random;

class GfG {  
    
    // Partition function: Rearranges elements 
    // around a pivot (last element)
    static int partition(int[] arr, int l, int r) {  
        int x = arr[r];  
        int i = l;     

        // Iterate through the subarray
        for (int j = l; j <= r - 1; j++) {  
            
            // Move elements <= pivot to the left partition
            if (arr[j] <= x) {  
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++; 
            }  
        }  
        
        // Place the pivot in its correct position
        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
        return i;  
    }  

    // Randomizes the pivot to avoid worst-case performance
    static int randomPartition(int[] arr, int l, int r) {  
        Random rand = new Random();
        int n = r - l + 1;  
        int pivot = rand.nextInt(n);      
        int temp = arr[l + pivot];
        arr[l + pivot] = arr[r];
        arr[r] = temp;
        return partition(arr, l, r); 
    }  

    // function to find the k'th smallest element using QuickSelect
    static int quickSelect(int[] arr, int l, int r, int k) {  
        
        // Check if k is within the valid range of 
        // the current subarray
        if (k > 0 && k <= r - l + 1) {  
            
            // Partition the array and get the
            // pivot's final position
            int pos = randomPartition(arr, l, r);  

            // If pivot is the k'th element, return it
            if (pos - l == k - 1)  
                return arr[pos];  

            // If pivot's position is larger than k,
            // search left subarray
            if (pos - l > k - 1)  
                return quickSelect(arr, l, pos - 1, k);  

            // Otherwise, search right subarray and adjust k 
            // (k is reduced by the size of the left partition)
            return quickSelect(arr, pos + 1, r, k - (pos - l + 1));  
        }  
        
        // Return infinity for invalid k (error handling)
        return Integer.MAX_VALUE;  
    }

    static int kthSmallest(int[] arr, int k) {
        int n = arr.length;
        return quickSelect(arr, 0, n - 1, k);
    }

    public static void main(String[] args) {  
        int[] arr = {12, 3, 5, 7, 4, 19, 26};  
        int k = 3;  
        System.out.println(kthSmallest(arr, k));  
    }  
}

輸出
5
時(shí)間復(fù)雜度：O（n） 上述解的最壞情況下時(shí)間復(fù)雜度仍為 O（n2）。在最壞情況下，隨機(jī)函數(shù)可能總是選擇一個(gè)角元素。然而，平均情況下的時(shí)間復(fù)雜度為 。分析假設(shè)隨機(jī)數(shù)生成器生成輸入范圍內(nèi)任意數(shù)字的可能性相等。
輔助空間： 自使用常數(shù)變量以來(lái)，O（1）。O(n)

即使最壞時(shí)間復(fù)雜度是二次方，這種解在實(shí)際中也表現(xiàn)最佳。

編程資源
https://pan.quark.cn/s/7f7c83756948
更多資源
https://pan.quark.cn/s/bda57957c548