dsal 使用 STL 的第K个最小/最大元素

使用 STL 的第`K`个最小/最大元素

原文： https://www.geeksforgeeks.org/kth-smallestlargest-element-using-stl/

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

例子：

Input : arr[] = {7, 10, 4, 3, 20, 15}
            k = 2
Output : 4
Smallest element is 3\. Second smallest
is 4.

Input : arr[] = {7, 10, 4, 3, 3, 15}
            k = 2
Output : 4
Even if there are more than one occurrences
of 3, answer should be 4.

Input :arr[] = {7, 10, 4, 3, 20, 15}
          k = 4
Output : 10

我们使用在 C++ STL 中的集合。

将所有元素插入集合。
遍历设置并打印第k个元素。

// STL based C++ program to find k-th smallest 
// element. 
#include <bits/stdc++.h> 
using namespace std; 

int kthSmallest(int arr[], int n, int k) 
{ 
    // Insert all elements into the set 
    set<int> s; 
    for (int i = 0; i < n; i++) 
        s.insert(arr[i]); 

    // Traverse set and print k-th element 
    auto it = s.begin(); 
    for (int i = 0; i < k - 1; i++) 
        it++; 
    return *it; 
} 

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

输出：