dsal 未排序数组中第K个最小/最大元素 | 系列 1

未排序数组中第`K`个最小/最大元素 | 系列 1

原文： https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

给定一个数组和一个数k（其中k小于数组的大小），我们需要找到给定数组中第k个最小的元素。假定有 11 个数组元素是不同的。

示例：

输入: arr[] = {7, 10, 4, 4, 3, 20, 15}

k = 3

输出: 7

输入: arr[] = {7, 10, 4, 3, 20, 15}

k = 4

输出: 10

我们已经讨论了打印k个最大元素的类似的问题。

方法 1（简单解决方案）：

一个简单的解决方案是使用O(N log N)排序算法对给定数组进行排序，例如归并排序，堆排序等，并返回已排序数组中索引k-1处的元素。

该解决方案的时间复杂度为O(N log N)。

C++

// Simple C++ program to find k'th smallest element 
#include <algorithm> 
#include <iostream> 
using namespace std; 

// Function to return k'th smallest element in a given array 
int kthSmallest(int arr[], int n, int k) 
{ 
    // Sort the given array 
    sort(arr, arr + n); 

    // Return k'th element in the sorted array 
    return arr[k - 1]; 
} 

// Driver program to test above methods 
int main() 
{ 
    int arr[] = { 12, 3, 5, 7, 19 }; 
    int n = sizeof(arr) / sizeof(arr[0]), k = 2; 
    cout << "K'th smallest element is " << kthSmallest(arr, n, k); 
    return 0; 
}

Java

// Java code for kth smallest element 
// in an array 
import java.util.Arrays; 
import java.util.Collections; 

class GFG { 
    // Function to return k'th smallest 
    // element in a given array 
    public static int kthSmallest(Integer[] arr, 
                                  int k) 
    { 
        // Sort the given array 
        Arrays.sort(arr); 

        // Return k'th element in 
        // the sorted array 
        return arr[k - 1]; 
    } 

    // driver program 
    public static void main(String[] args) 
    { 
        Integer arr[] = new Integer[] { 12, 3, 5, 7, 19 }; 
        int k = 2; 
        System.out.print("K'th smallest element is " + kthSmallest(arr, k)); 
    } 
} 

// This code is contributed by Chhavi

Python3

# Python3 program to find k'th smallest 
# element  

# Function to return k'th smallest  
# element in a given array  
def kthSmallest(arr, n, k): 

    # Sort the given array  
    arr.sort() 

    # Return k'th element in the  
    # sorted array  
    return arr[k-1] 

# Driver code 
if __name__=='__main__': 
    arr = [12, 3, 5, 7, 19] 
    n = len(arr) 
    k = 2
    print("K'th smallest element is", 
          kthSmallest(arr, n, k)) 

# This code is contributed by  
# Shrikant13

C#

// C# code for kth smallest element 
// in an array 
using System; 

class GFG { 

    // Function to return k'th smallest 
    // element in a given array 
    public static int kthSmallest(int[] arr, 
                                  int k) 
    { 

        // Sort the given array 
        Array.Sort(arr); 

        // Return k'th element in 
        // the sorted array 
        return arr[k - 1]; 
    } 

    // driver program 
    public static void Main() 
    { 
        int[] arr = new int[] { 12, 3, 5, 
                                7, 19 }; 
        int k = 2; 
        Console.Write("K'th smallest element"
                      + " is " + kthSmallest(arr, k)); 
    } 
} 

// This code is contributed by nitin mittal.

PHP

<?php 
// Simple PHP program to find  
// k'th smallest element 

// Function to return k'th smallest 
// element in a given array 
function kthSmallest($arr, $n, $k) 
{ 

    // Sort the given array 
    sort($arr); 

    // Return k'th element  
    // in the sorted array 
    return $arr[$k - 1]; 
} 

    // Driver Code 
    $arr = array(12, 3, 5, 7, 19); 
    $n =count($arr); 
    $k = 2; 
    echo "K'th smallest element is ", kthSmallest($arr, $n, $k); 

// This code is contributed by anuj_67\. 
?>

输出：

K'th smallest element is 5

方法 2（使用最小堆 – 堆选择）：

我们发现时间复杂度中的第k个最小元素要好于O(N log N)。一个简单的优化方法是创建给定n个元素的最小堆，并调用k次extractMin()。

以下是上述方法的 C++ 实现。

// A C++ program to find k'th smallest element using min heap 
#include <climits> 
#include <iostream> 
using namespace std; 

// Prototype of a utility function to swap two integers 
void swap(int* x, int* y); 

// A class for Min Heap 
class MinHeap { 
    int* harr; // pointer to array of elements in heap 
    int capacity; // maximum possible size of min heap 
    int heap_size; // Current number of elements in min heap 
public: 
    MinHeap(int a[], int size); // Constructor 
    void MinHeapify(int i); // To minheapify subtree rooted with index i 
    int parent(int i) { return (i - 1) / 2; } 
    int left(int i) { return (2 * i + 1); } 
    int right(int i) { return (2 * i + 2); } 

    int extractMin(); // extracts root (minimum) element 
    int getMin() { return harr[0]; } // Returns minimum 
}; 

MinHeap::MinHeap(int a[], int size) 
{ 
    heap_size = size; 
    harr = a; // store address of array 
    int i = (heap_size - 1) / 2; 
    while (i >= 0) { 
        MinHeapify(i); 
        i--; 
    } 
} 

// Method to remove minimum element (or root) from min heap 
int MinHeap::extractMin() 
{ 
    if (heap_size == 0) 
        return INT_MAX; 

    // Store the minimum vakue. 
    int root = harr[0]; 

    // If there are more than 1 items, move the last item to root 
    // and call heapify. 
    if (heap_size > 1) { 
        harr[0] = harr[heap_size - 1]; 
        MinHeapify(0); 
    } 
    heap_size--; 

    return root; 
} 

// A recursive method to heapify a subtree with root at given index 
// This method assumes that the subtrees are already heapified 
void MinHeap::MinHeapify(int i) 
{ 
    int l = left(i); 
    int r = right(i); 
    int smallest = i; 
    if (l < heap_size && harr[l] < harr[i]) 
        smallest = l; 
    if (r < heap_size && harr[r] < harr[smallest]) 
        smallest = r; 
    if (smallest != i) { 
        swap(&harr[i], &harr[smallest]); 
        MinHeapify(smallest); 
    } 
} 

// A utility function to swap two elements 
void swap(int* x, int* y) 
{ 
    int temp = *x; 
    *x = *y; 
    *y = temp; 
} 

// Function to return k'th smallest element in a given array 
int kthSmallest(int arr[], int n, int k) 
{ 
    // Build a heap of n elements: O(n) time 
    MinHeap mh(arr, n); 

    // Do extract min (k-1) times 
    for (int i = 0; i < k - 1; i++) 
        mh.extractMin(); 

    // Return root 
    return mh.getMin(); 
} 

// Driver program to test above methods 
int main() 
{ 
    int arr[] = { 12, 3, 5, 7, 19 }; 
    int n = sizeof(arr) / sizeof(arr[0]), k = 2; 
    cout << "K'th smallest element is " << kthSmallest(arr, n, k); 
    return 0; 
}

输出：

K'th smallest element is 5

该解决方案的时间复杂度为O(n + kLogn)。

方法 3（使用最大堆）：

我们也可以使用最大堆来找到第k个最小元素。以下是算法。

建立给定数组的前k个元素（arr[0]至arr[k-1]）的最大堆MH。
对于每个元素，在第k个元素之后（arr[k]至arr[n-1]），将其与MH的根进行比较。
1. 如果元素小于根，则将其设为根并为MH调用建堆，
2. 否则将其忽略。

步骤 2 为O((n-k) * logk)。

最后，MH的根是第k个最小元素。

该解决方案的时间复杂度为O(k + (n-k) * Logk)。

以下是上述算法的 C++ 实现：

// A C++ program to find k'th smallest element using max heap 
#include <climits> 
#include <iostream> 
using namespace std; 

// Prototype of a utility function to swap two integers 
void swap(int* x, int* y); 

// A class for Max Heap 
class MaxHeap { 
    int* harr; // pointer to array of elements in heap 
    int capacity; // maximum possible size of max heap 
    int heap_size; // Current number of elements in max heap 
public: 
    MaxHeap(int a[], int size); // Constructor 
    void maxHeapify(int i); // To maxHeapify subtree rooted with index i 
    int parent(int i) { return (i - 1) / 2; } 
    int left(int i) { return (2 * i + 1); } 
    int right(int i) { return (2 * i + 2); } 

    int extractMax(); // extracts root (maximum) element 
    int getMax() { return harr[0]; } // Returns maximum 

    // to replace root with new node x and heapify() new root 
    void replaceMax(int x) 
    { 
        harr[0] = x; 
        maxHeapify(0); 
    } 
}; 

MaxHeap::MaxHeap(int a[], int size) 
{ 
    heap_size = size; 
    harr = a; // store address of array 
    int i = (heap_size - 1) / 2; 
    while (i >= 0) { 
        maxHeapify(i); 
        i--; 
    } 
} 

// Method to remove maximum element (or root) from max heap 
int MaxHeap::extractMax() 
{ 
    if (heap_size == 0) 
        return INT_MAX; 

    // Store the maximum vakue. 
    int root = harr[0]; 

    // If there are more than 1 items, move the last item to root 
    // and call heapify. 
    if (heap_size > 1) { 
        harr[0] = harr[heap_size - 1]; 
        maxHeapify(0); 
    } 
    heap_size--; 

    return root; 
} 

// A recursive method to heapify a subtree with root at given index 
// This method assumes that the subtrees are already heapified 
void MaxHeap::maxHeapify(int i) 
{ 
    int l = left(i); 
    int r = right(i); 
    int largest = i; 
    if (l < heap_size && harr[l] > harr[i]) 
        largest = l; 
    if (r < heap_size && harr[r] > harr[largest]) 
        largest = r; 
    if (largest != i) { 
        swap(&harr[i], &harr[largest]); 
        maxHeapify(largest); 
    } 
} 

// A utility function to swap two elements 
void swap(int* x, int* y) 
{ 
    int temp = *x; 
    *x = *y; 
    *y = temp; 
} 

// Function to return k'th largest element in a given array 
int kthSmallest(int arr[], int n, int k) 
{ 
    // Build a heap of first k elements: O(k) time 
    MaxHeap mh(arr, k); 

    // Process remaining n-k elements.  If current element is 
    // smaller than root, replace root with current element 
    for (int i = k; i < n; i++) 
        if (arr[i] < mh.getMax()) 
            mh.replaceMax(arr[i]); 

    // Return root 
    return mh.getMax(); 
} 

// Driver program to test above methods 
int main() 
{ 
    int arr[] = { 12, 3, 5, 7, 19 }; 
    int n = sizeof(arr) / sizeof(arr[0]), k = 4; 
    cout << "K'th smallest element is " << kthSmallest(arr, n, k); 
    return 0; 
}

输出：

K'th smallest element is 12

方法 4（快速选择）：

如果在第一步中将快速排序用作排序算法，则这是对方法 1 的优化。在快速排序中，我们选择一个枢轴元素，然后将枢轴元素移动到正确的位置并围绕该数组对其进行分区。这个想法不是要进行完整的快速排序，而是停在枢轴本身是第k个最小元素的位置。同样，不要针对枢轴的左侧和右侧重复出现，而是根据枢轴的位置针对其中之一进行重复播放。该方法最坏的情况是时间复杂度为 O(n^2)，但平均而言，它的工作时间为O(n)。

C++

#include <climits> 
#include <iostream> 
using namespace std; 

int partition(int arr[], int l, int r); 

// This function returns k'th smallest element in arr[l..r] using 
// QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT 
int kthSmallest(int arr[], int l, int r, int k) 
{ 
    // If k is smaller than number of elements in array 
    if (k > 0 && k <= r - l + 1) { 
        // Partition the array around last element and get 
        // position of pivot element in sorted array 
        int pos = partition(arr, l, r); 

        // If position is same as k 
        if (pos - l == k - 1) 
            return arr[pos]; 
        if (pos - l > k - 1) // If position is more, recur for left subarray 
            return kthSmallest(arr, l, pos - 1, k); 

        // Else recur for right subarray 
        return kthSmallest(arr, pos + 1, r, k - pos + l - 1); 
    } 

    // If k is more than number of elements in array 
    return INT_MAX; 
} 

void swap(int* a, int* b) 
{ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 

// Standard partition process of QuickSort().  It considers the last 
// element as pivot and moves all smaller element to left of it 
// and greater elements to right 
int partition(int arr[], int l, int r) 
{ 
    int x = arr[r], i = l; 
    for (int j = l; j <= r - 1; j++) { 
        if (arr[j] <= x) { 
            swap(&arr[i], &arr[j]); 
            i++; 
        } 
    } 
    swap(&arr[i], &arr[r]); 
    return i; 
} 

// Driver program to test above methods 
int main() 
{ 
    int arr[] = { 12, 3, 5, 7, 4, 19, 26 }; 
    int n = sizeof(arr) / sizeof(arr[0]), k = 3; 
    cout << "K'th smallest element is " << kthSmallest(arr, 0, n - 1, k); 
    return 0; 
}

Java

// Java code for kth smallest element in an array 
import java.util.Arrays; 
import java.util.Collections; 

class GFG { 
    // Standard partition process of QuickSort. 
    // It considers the last element as pivot 
    // and moves all smaller element to left of 
    // it and greater elements to right 
    public static int partition(Integer[] arr, int l, 
                                int r) 
    { 
        int x = arr[r], i = l; 
        for (int j = l; j <= r - 1; j++) { 
            if (arr[j] <= x) { 
                // Swapping arr[i] and arr[j] 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 

                i++; 
            } 
        } 

        // Swapping arr[i] and arr[r] 
        int temp = arr[i]; 
        arr[i] = arr[r]; 
        arr[r] = temp; 

        return i; 
    } 

    // This function returns k'th smallest element 
    // in arr[l..r] using QuickSort based method. 
    // ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT 
    public static int kthSmallest(Integer[] arr, int l, 
                                  int r, int k) 
    { 
        // If k is smaller than number of elements 
        // in array 
        if (k > 0 && k <= r - l + 1) { 
            // Partition the array around last 
            // element and get position of pivot 
            // element in sorted array 
            int pos = partition(arr, l, r); 

            // If position is same as k 
            if (pos - l == k - 1) 
                return arr[pos]; 

            // If position is more, recur for 
            // left subarray 
            if (pos - l > k - 1) 
                return kthSmallest(arr, l, pos - 1, k); 

            // Else recur for right subarray 
            return kthSmallest(arr, pos + 1, r, k - pos + l - 1); 
        } 

        // If k is more than number of elements 
        // in array 
        return Integer.MAX_VALUE; 
    } 

    // Driver program to test above methods 
    public static void main(String[] args) 
    { 
        Integer arr[] = new Integer[] { 12, 3, 5, 7, 4, 19, 26 }; 
        int k = 3; 
        System.out.print("K'th smallest element is " + kthSmallest(arr, 0, arr.length - 1, k)); 
    } 
} 

// This code is contributed by Chhavi

Python 3

# This function returns k'th smallest element  
# in arr[l..r] using QuickSort based method.  
# ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT 
import sys 

def kthSmallest(arr, l, r, k): 

    # If k is smaller than number of  
    # elements in array 
    if (k > 0 and k <= r - l + 1): 

        # Partition the array around last  
        # element and get position of pivot 
        # element in sorted array 
        pos = partition(arr, l, r) 

        # If position is same as k 
        if (pos - l == k - 1): 
            return arr[pos] 
        if (pos - l > k - 1): # If position is more,  
                              # recur for left subarray 
            return kthSmallest(arr, l, pos - 1, k) 

        # Else recur for right subarray 
        return kthSmallest(arr, pos + 1, r, 
                            k - pos + l - 1) 

    # If k is more than number of 
    # elements in array 
    return sys.maxsize 

# Standard partition process of QuickSort().  
# It considers the last element as pivot and 
# moves all smaller element to left of it 
# and greater elements to right 
def partition(arr, l, r): 

    x = arr[r] 
    i = l 
    for j in range(l, r): 
        if (arr[j] <= x): 
            arr[i], arr[j] = arr[j], arr[i] 
            i += 1
    arr[i], arr[r] = arr[r], arr[i] 
    return i 

# Driver Code 
if __name__ == "__main__": 

    arr = [12, 3, 5, 7, 4, 19, 26] 
    n = len(arr) 
    k = 3; 
    print("K'th smallest element is",  
           kthSmallest(arr, 0, n - 1, k)) 

# This code is contributed by ita_c

C

// C# code for kth smallest element 
// in an array 
using System; 

class GFG { 

    // Standard partition process of QuickSort. 
    // It considers the last element as pivot 
    // and moves all smaller element to left of 
    // it and greater elements to right 
    public static int partition(int[] arr, 
                                int l, int r) 
    { 
        int x = arr[r], i = l; 
        int temp = 0; 
        for (int j = l; j <= r - 1; j++) { 

            if (arr[j] <= x) { 
                // Swapping arr[i] and arr[j] 
                temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 

                i++; 
            } 
        } 

        // Swapping arr[i] and arr[r] 
        temp = arr[i]; 
        arr[i] = arr[r]; 
        arr[r] = temp; 

        return i; 
    } 

    // This function returns k'th smallest 
    // element in arr[l..r] using QuickSort 
    // based method. ASSUMPTION: ALL ELEMENTS 
    // IN ARR[] ARE DISTINCT 
    public static int kthSmallest(int[] arr, int l, 
                                  int r, int k) 
    { 
        // If k is smaller than number 
        // of elements in array 
        if (k > 0 && k <= r - l + 1) { 
            // Partition the array around last 
            // element and get position of pivot 
            // element in sorted array 
            int pos = partition(arr, l, r); 

            // If position is same as k 
            if (pos - l == k - 1) 
                return arr[pos]; 

            // If position is more, recur for 
            // left subarray 
            if (pos - l > k - 1) 
                return kthSmallest(arr, l, pos - 1, k); 

            // Else recur for right subarray 
            return kthSmallest(arr, pos + 1, r, 
                               k - pos + l - 1); 
        } 

        // If k is more than number 
        // of elements in array 
        return int.MaxValue; 
    } 

    // Driver Code 
    public static void Main() 
    { 
        int[] arr = { 12, 3, 5, 7, 4, 19, 26 }; 
        int k = 3; 
        Console.Write("K'th smallest element is " + kthSmallest(arr, 0, arr.Length - 1, k)); 
    } 
} 

// This code is contributed 
// by 29AjayKumar

输出：

K'th smallest element is 5

有两种以上的解决方案比上面讨论的解决方案更好：一种解决方案是对quickSelect()进行随机化处理，另一种解决方案是最坏情况的线性时间算法（请参阅以下文章）。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/36127.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

分类

最近更新

dsal 未排序数组中第K个最小/最大元素 | 系列 1

未排序数组中第`K`个最小/最大元素 | 系列 1

C++

Java

Python3

C#

PHP

C++

Java

Python 3

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

dsal 未排序数组中第K个最小/最大元素 | 系列 1

未排序数组中第K个最小/最大元素 | 系列 1

C++

Java

Python3

C#

PHP

C++

Java

Python 3

C

留言

联系客服

dsal 查看更多书籍

未排序数组中第`K`个最小/最大元素 | 系列 1