右边最小的大元素-yiteyi-C++库

3给定一个不同元素的数组，为每个元素打印最接近的较大元素。元素X最接近的元素是数组中X的右边的最小元素，它大于x。元素没有更大的元素存在，考虑下一个更大的元素为-1。 例如：

null

Input: arr[] = {4, 5, 2, 25}Output: Element       NGE   4      -->   5   5      -->   25   2      -->   25   25     -->   -1Input: arr[] = {4, 10, 7}Output: Element       NGE   4       -->  7   10      -->   -1   7       -->   -1

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

方法： 在本文中，我们将讨论如何使用C++ STL查找下一个更大的元素。设置 ). 在右边查找最小的较大元素就像在排序的列表中查找当前元素的第一个较大元素一样。考虑示例1，排序列表看起来像2, 4, 5、25。这里对于元素4，较大的元素是5，因为它在它旁边，所以我们打印5并删除4，因为它不会比其他元素大，因为它不再位于任何人的右边。同样，对于5，它是25，我们从列表中删除5，因为5不会在2或25的右侧，所以可以删除它。下面给出了在每个索引元素中查找下一个更大元素的步骤。

将所有元素插入到设置，它将以递增的顺序存储所有元素。
迭代元素数组，并为每个索引找到上界当前索引元素的。上限（）返回一个迭代器，该迭代器可以指向以下位置。
1. 如果迭代器指向超过最后一个元素的位置，则当前索引元素不存在NGE。
2. 如果迭代器指向一个引用元素的位置，那么该元素就是当前索引元素的NGE。
在每次遍历时找到当前索引元素的位置，并使用set的>lower_bound（）和erase（）函数将其从集合中移除。

以下是上述方法的实施情况。

C++

                         // C++ program to print the                       
                         // NGE's of array elements using                       
                         // C++ STL                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to print the NGE                       
                         void                                     printNGE(                                     int                                     a[],                                     int                                     n)                       
                         {                       
           
                                                 set<                                     int                                     > ms;                       
           
                                                 // insert in the multiset container                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 ms.insert(a[i]);                       
           
                                                 cout <<                                     "Element "                       
                                                 <<                                     "NGE"                                     ;                       
           
                                                 // traverse for all array elements                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // find the upper_bound in set                       
                                                 auto                                     it = ms.upper_bound(a[i]);                       
           
                                                 // if points to the end, then                       
                                                 // no NGE of that element                       
                                                 if                                     (it == ms.end()) {                       
                                                 cout <<                                     " "                                     << a[i]                       
                                                 <<                                     " ----> "                                     << -1;                       
                                                 }                       
           
                                                 // print the element at that position                       
                                                 else                                     {                       
                                                 cout <<                                     " "                                     << a[i]                       
                                                 <<                                     " ----> "                                     << *it;                       
                                                 }                       
           
                                                 // find the first occurrence of                       
                                                 // the index element and delete it                       
                                                 it = ms.lower_bound(a[i]);                       
           
                                                 // delete one occurrence                       
                                                 // from the container                       
                                                 ms.erase(it);                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 4, 5, 2, 25 };                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
           
                                                 // Function call to print the NGE                       
                                                 printNGE(a, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // C++ program to print the                       
                         // NGE's of array elements using                       
                         import                                     java.util.TreeSet;                       
           
                         class                                     Geeks {                       
           
                                                 // Function to print the NGE                       
                                                 static                                     void                                     printNGE(                                     int                                     [] a,                                     int                                     n)                       
                                                 {                       
           
                                                 // Tree Set is an ordered set used to                       
                                                 // store elements in a sorted manner                       
                                                 TreeSet<Integer> t =                                     new                                     TreeSet<>();                       
           
                                                 // Adding elements into the set                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 t.add(a[i]);                       
           
                                                 System.out.println(                                     "ELEMENT     NGE"                                     );                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
           
                                                 // If the elements does not have an upper bound                       
                                                 // or an element greater than it,                       
                                                 // higher method of TreeSet class will return NULL                       
                                                 if                                     (t.higher(a[i]) ==                                     null                                     )                       
                                                 System.out.println(a[i] +                                     " ----> "                       
                                                 +                                     "-1"                                     );                       
           
                                                 // Otherwise print the upper bound of that element                       
                                                 else                       
                                                 System.out.println(a[i] +                                     " ----> "                                     + t.higher(a[i]));                       
           
                                                 // Remove the current element from the set                       
                                                 t.remove(a[i]);                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 int                                     a[] = {                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     25                                     };                       
                                                 int                                     n = a.length;                       
           
                                                 printNGE(a, n);                       
                                                 }                       
                         }                       

Python3

                         # Python3 program to print the                       
                         # NGE's of array elements                       
                         from                                     bisect                                     import                                     bisect_right as upper_bound,                       
                                                 bisect_left as lower_bound                       
           
                         # Function to print the NGE                       
                         def                                     printNGE(a:                                     list                                     , n):                       
                                                 ms                                     =                                     set                                     ()                       
           
                                                 # insert in the multiset container                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 ms.add(a[i])                       
           
                                                 print                                     (                                     "Element NGE"                                     , end                                     =                                     "")                       
           
                                                 # Required because Python sets                       
                                                 # are not sorted                       
                                                 new_arr                                     =                                     list                                     (ms)                       
                                                 new_arr.sort()                       
           
                                                 # traverse for all array elements                       
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # find the upper_bound in set                       
                                                 it                                     =                                     upper_bound(new_arr, a[i])                       
           
                                                 # if points to the end, then                       
                                                 # no NGE of that element                       
                                                 if                                     (it                                     =                                     =                                     len                                     (new_arr)):                       
                                                 print                                     (                                     " %d ----> -1"                                     %                                     a[i], end                                     =                                     "")                       
           
                                                 # print the element at that position                       
                                                 else                                     :                       
                                                 print                                     (                                     " %d ----> %d"                                     %                                     (a[i],                       
                                                 new_arr[it]), end                                     =                                     "")                       
           
                                                 # find the first occurrence of                       
                                                 # the index element and delete it                       
                                                 it                                     =                                     lower_bound(new_arr, a[i])                       
           
                                                 # delete one occurrence                       
                                                 # from the container                       
                                                 new_arr.remove(new_arr[it])                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 a                                     =                                     [                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     25                                     ]                       
                                                 n                                     =                                     len                                     (a)                       
           
                                                 # Function call to print the NGE                       
                                                 printNGE(a, n)                       
           
                         # This code is contributed by                       
                         # sanjeev2552                       

Javascript

                         <script>                       
                         // Javascript program to print the                       
                         // NGE's of array elements using                       
           
                                                 // Function to print the NGE                       
                                                 function                                     printNGE(a , n) {                       
           
                                                 // Tree Set is an ordered set used to                       
                                                 // store elements in a sorted manner                       
                                                 var                                     t =                                     new                                     Set();                       
           
                                                 // Adding elements into the set                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++)                       
                                                 t.add(a[i]);                       
           
                                                 document.write(                                     "ELEMENT     NGE<br/>"                                     );                       
           
                                                 for                                     (i = 0; i < n; i++) {                       
           
                                                 // If the elements does not have an upper bound                       
                                                 // or an element greater than it,                       
                                                 // higher method of TreeSet class will return NULL                       
                                                 if                                     (upper_bound(t,a[i]) ==                                     null                                     )                       
                                                 document.write(a[i] +                                     " ----> "                                     +                                     "-1"                                     +                                     "<br/>"                                     );                       
           
                                                 // Otherwise print the upper bound of that element                       
                                                 else                       
                                                 document.write(a[i] +                                     " ----> "                                     + upper_bound(t,a[i])+                                     "<br/>"                                     );                       
           
                                                 // Remove the current element from the set                       
                                                 t.                                     delete                                     (a[i]);                       
                                                 }                       
                                                 }                       
                                                 function                                     upper_bound(s, val)                       
                                                 {                       
                                                 let temp = [...s];                       
                                                 temp.sort((a, b) => b - a);                       
                                                 return                                     temp[temp.indexOf(val) + 1];                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 var                                     a = [ 4, 5, 2, 25 ];                       
                                                 var                                     n = a.length;                       
           
                                                 printNGE(a, n);                       
           
                         // This code contributed by Rajput-Ji                       
                         </script>                       

输出：

Element   NGE   4 ----> 5   5 ----> 25   2 ----> 25   25 ----> -1

时间复杂性： O（N日志N）

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

THE END

技术文章