使用STL的第K个最小/最大元素-yiteyi-C++库

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

null

例如：

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们使用在C++ STL中设置 . 1）将所有元素插入一个集合。 2）遍历集合并打印第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;                   
                     }                   

输出：

K'th smallest element is 5

上述解的时间复杂度为O（n logn）。请注意，STL中的set在内部使用自平衡BST，因此搜索和插入操作的时间复杂度为O（logn）。

本文由 罗山·哈尔瓦伊 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章