将其右边的每个较大元素替换为最小元素-yiteyi-C++库

给定一个整数数组，用数组中右边最小的元素替换每个元素。如果右侧没有更大的元素，请将其替换为-1。

null

例如：

Input: [8, 58, 71, 18, 31, 32, 63, 92,          43, 3, 91, 93, 25, 80, 28]Output: [18, 63, 80, 25, 32, 43, 80, 93,          80, 25, 93, -1, 28, -1, -1]

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

一个简单的方法是运行两个循环。外部循环将从左到右逐个拾取数组元素。内部循环将在其右侧找到比拾取的元素大的最小元素。最后，外循环将用内循环找到的元素替换拾取的元素。该方法的时间复杂度为O（n） ^2. ).

一个棘手的解决方案是使用二进制搜索树。我们开始从右到左扫描数组，并将每个元素插入BST。对于每个插入的元素，我们将其替换为BST中的顺序后继元素。如果插入的元素是迄今为止的最大值（即其顺序后继元素不存在），我们将其替换为-1。

以下是上述理念的实施情况——

C++

                         // C++ program to replace every element with the                       
                         // least greater element on its right                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A binary Tree node                       
                         struct                                     Node {                       
                                                 int                                     data;                       
                                                 Node *left, *right;                       
                         };                       
           
                         // A utility function to create a new BST node                       
                         Node* newNode(                                     int                                     item)                       
                         {                       
                                                 Node* temp =                                     new                                     Node;                       
                                                 temp->data = item;                       
                                                 temp->left = temp->right = NULL;                       
           
                                                 return                                     temp;                       
                         }                       
           
                         /* A utility function to insert a new node with                       
                                                 given data in BST and find its successor */                       
                         Node* insert(Node* node,                                     int                                     data, Node*& succ)                       
                         {                       
                                   
                                                 /* If the tree is empty, return a new node */                       
                                                 if                                     (node == NULL)                       
                                                 return                                     node = newNode(data);                       
           
                                                 // If key is smaller than root's key, go to left                       
                                                 // subtree and set successor as current node                       
                                                 if                                     (data < node->data) {                       
                                                 succ = node;                       
                                                 node->left = insert(node->left, data, succ);                       
                                                 }                       
           
                                                 // go to right subtree                       
                                                 else                                     if                                     (data > node->data)                       
                                                 node->right = insert(node->right, data, succ);                       
                                                 return                                     node;                       
                         }                       
           
                         // Function to replace every element with the                       
                         // least greater element on its right                       
                         void                                     replace(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 Node* root = NULL;                       
           
                                                 // start from right to left                       
                                                 for                                     (                                     int                                     i = n - 1; i >= 0; i--) {                       
                                                 Node* succ = NULL;                       
           
                                                 // insert current element into BST and                       
                                                 // find its inorder successor                       
                                                 root = insert(root, arr[i], succ);                       
           
                                                 // replace element by its inorder                       
                                                 // successor in BST                       
                                                 if                                     (succ)                       
                                                 arr[i] = succ->data;                       
                                                 else                                     // No inorder successor                       
                                                 arr[i] = -1;                       
                                                 }                       
                         }                       
           
                         // Driver Program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 8,  58, 71, 18, 31, 32, 63, 92,                       
                                                 43, 3,  91, 93, 25, 80, 28 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 replace(arr, n);                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to replace every element with                       
                         // the least greater element on its right                       
                         import                                     java.io.*;                       
           
                         class                                     BinarySearchTree{                       
                                   
                         // A binary Tree node                       
                         class                                     Node                       
                         {                       
                                                 int                                     data;                       
                                                 Node left, right;                       
           
                                                 Node(                                     int                                     d)                       
                                                 {                       
                                                 data = d;                       
                                                 left = right =                                     null                                     ;                       
                                                 }                       
                         }                       
           
                         // Root of BST                       
                         static                                     Node root;                       
                         static                                     Node succ;                       
           
                         // Constructor                       
                         BinarySearchTree()                       
                         {                       
                                                 root =                                     null                                     ;                       
                                                 succ =                                     null                                     ;                       
                         }                       
           
                         // A utility function to insert a new node with                       
                         // given data in BST and find its successor                       
                         Node insert(Node node,                                     int                                     data)                       
                         {                       
                                   
                                                 // If the tree is empty, return a new node                       
                                                 if                                     (node ==                                     null                                     )                       
                                                 {                       
                                                 node =                                     new                                     Node(data);                       
                                                 }                       
           
                                                 // If key is smaller than root's key,                       
                                                 // go to left subtree and set successor                       
                                                 // as current node                       
                                                 if                                     (data < node.data)                       
                                                 {                       
                                                 succ = node;                       
                                                 node.left = insert(node.left, data);                       
                                                 }                       
           
                                                 // Go to right subtree                       
                                                 else                                     if                                     (data > node.data)                       
                                                 node.right = insert(node.right, data);                       
                                   
                                                 return                                     node;                       
                         }                       
           
                         // Function to replace every element with the                       
                         // least greater element on its right                       
                         static                                     void                                     replace(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 BinarySearchTree tree =                                     new                                     BinarySearchTree();                       
           
                                                 // start from right to left                       
                                                 for                                     (                                     int                                     i = n -                                     1                                     ; i >=                                     0                                     ; i--)                       
                                                 {                       
                                                 succ =                                     null                                     ;                       
                                   
                                                 // Insert current element into BST and                       
                                                 // find its inorder successor                       
                                                 root = tree.insert(root, arr[i]);                       
           
                                                 // Replace element by its inorder                       
                                                 // successor in BST                       
                                                 if                                     (succ !=                                     null                                     )                       
                                                 arr[i] = succ.data;                       
                                   
                                                 // No inorder successor                       
                                                 else                       
                                                 arr[i] = -                                     1                                     ;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     arr[] =                                     new                                     int                                     [] {                                     8                                     ,                                     58                                     ,                                     71                                     ,                                     18                                     ,                                     31                                     ,                       
                                                 32                                     ,                                     63                                     ,                                     92                                     ,                                     43                                     ,                                     3                                     ,                       
                                                 91                                     ,                                     93                                     ,                                     25                                     ,                                     80                                     ,                                     28                                     };                       
                                                 int                                     n = arr.length;                       
           
                                                 replace(arr, n);                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                         }                       
                         }                       
           
                         // The code is contributed by Tushar Bansal                       

Python3

                         # Python3 program to replace every element                       
                         # with the least greater element on its right                       
           
                         # A binary Tree node                       
                         class                                     Node:                       
                                   
                                                 def                                     __init__(                                     self                                     , d):                       
                                   
                                                 self                                     .data                                     =                                     d                       
                                                 self                                     .left                                     =                                     None                       
                                                 self                                     .right                                     =                                     None                       
           
                         # A utility function to insert a new node with                       
                         # given data in BST and find its successor                       
                         def                                     insert(node, data):                       
                                   
                                                 global                                     succ                       
                                   
                                                 # If the tree is empty, return a new node                       
                                                 root                                     =                                     node                       
           
                                                 if                                     (node                                     =                                     =                                     None                                     ):                       
                                                 return                                     Node(data)                       
           
                                                 # If key is smaller than root's key, go to left                       
                                                 # subtree and set successor as current node                       
                                                 if                                     (data < node.data):                       
                                   
                                                 #print("1")                       
                                                 succ                                     =                                     node                       
                                                 root.left                                     =                                     insert(node.left, data)                       
           
                                                 # Go to right subtree                       
                                                 elif                                     (data > node.data):                       
                                                 root.right                                     =                                     insert(node.right, data)                       
                                   
                                                 return                                     root                       
           
                         # Function to replace every element with the                       
                         # least greater element on its right                       
                         def                                     replace(arr, n):                       
                                   
                                                 global                                     succ                       
                                                 root                                     =                                     None                       
           
                                                 # Start from right to left                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 succ                                     =                                     None                       
           
                                                 # Insert current element into BST and                       
                                                 # find its inorder successor                       
                                                 root                                     =                                     insert(root, arr[i])                       
           
                                                 # Replace element by its inorder                       
                                                 # successor in BST                       
                                                 if                                     (succ):                       
                                                 arr[i]                                     =                                     succ.data                       
                                   
                                                 # No inorder successor                       
                                                 else                                     :                       
                                                 arr[i]                                     =                                     -                                     1                       
                                   
                                                 return                                     arr                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                   
                                                 arr                                     =                                     [                                     8                                     ,                                     58                                     ,                                     71                                     ,                                     18                                     ,                                     31                                     ,                                     32                                     ,                                     63                                     ,                       
                                                 92                                     ,                                     43                                     ,                                     3                                     ,                                     91                                     ,                                     93                                     ,                                     25                                     ,                                     80                                     ,                                     28                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 succ                                     =                                     None                       
           
                                                 arr                                     =                                     replace(arr, n)                       
           
                                                 print                                     (                                     *                                     arr)                       
           
                         # This code is contributed by mohit kumar 29                       

C#

                         // C# program to replace every element with                       
                         // the least greater element on its right                       
                         using                                     System;                       
           
                         class                                     BinarySearchTree{                       
                                   
                         // A binary Tree node                       
                         public                                     class                                     Node                       
                         {                       
                                                 public                                     int                                     data;                       
                                                 public                                     Node left, right;                       
                                   
                                                 public                                     Node(                                     int                                     d)                       
                                                 {                       
                                                 data = d;                       
                                                 left = right =                                     null                                     ;                       
                                                 }                       
                         }                       
           
                         // Root of BST                       
                         public                                     static                                     Node root;                       
                         public                                     static                                     Node succ;                       
           
                         // Constructor                       
                         public                                     BinarySearchTree()                       
                         {                       
                                                 root =                                     null                                     ;                       
                                                 succ =                                     null                                     ;                       
                         }                       
           
                         // A utility function to insert a new node with                       
                         // given data in BST and find its successor                       
                         public                                     static                                     Node insert(Node node,                                     int                                     data)                       
                         {                       
                                   
                                                 // If the tree is empty, return a new node                       
                                                 if                                     (node ==                                     null                                     )                       
                                                 {                       
                                                 node =                                     new                                     Node(data);                       
                                                 }                       
                                   
                                                 // If key is smaller than root's key,                       
                                                 // go to left subtree and set successor                       
                                                 // as current node                       
                                                 if                                     (data < node.data)                       
                                                 {                       
                                                 succ = node;                       
                                                 node.left = insert(node.left, data);                       
                                                 }                       
                                   
                                                 // Go to right subtree                       
                                                 else                                     if                                     (data > node.data)                       
                                                 {                       
                                                 node.right = insert(node.right, data);                       
                                                 }                       
                                                 return                                     node;                       
                         }                       
           
                         // Function to replace every element with the                       
                         // least greater element on its right                       
                         public                                     static                                     void                                     replace(                                     int                                     [] arr,                                     int                                     n)                       
                         {                       
                                                 //BinarySearchTree tree = new BinarySearchTree();                       
                                                 // Start from right to left                       
                                                 for                                     (                                     int                                     i = n - 1; i >= 0; i--)                       
                                                 {                       
                                                 succ =                                     null                                     ;                       
                                   
                                                 // Insert current element into BST and                       
                                                 // find its inorder successor                       
                                                 root = BinarySearchTree.insert(root, arr[i]);                       
                                   
                                                 // Replace element by its inorder                       
                                                 // successor in BST                       
                                                 if                                     (succ !=                                     null                                     )                       
                                                 {                       
                                                 arr[i] = succ.data;                       
                                                 }                       
                                   
                                                 // No inorder successor                       
                                                 else                       
                                                 {                       
                                                 arr[i] = -1;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         static                                     public                                     void                                     Main()                       
                         {                       
                                                 int                                     [] arr = { 8, 58, 71, 18, 31,                       
                                                 32, 63, 92, 43, 3,                       
                                                 91, 93, 25, 80, 28 };                       
                                                 int                                     n = arr.Length;                       
                                   
                                                 replace(arr, n);                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 Console.Write(arr[i]+                                     " "                                     );                       
                                                 }                       
                         }                       
                         }                       
           
                         // This code is contributed by rag2127                       

Javascript

                         <script>                       
           
                         // Javascript program to                       
                         // replace every element with                       
                         // the least greater element                       
                         // on its right                       
                                   
                                                 // A binary Tree node                       
                                                 class Node{                       
                                                 constructor(d)                       
                                                 {                       
                                                 this                                     .data=d;                       
                                                 this                                     .left=                                     this                                     .right=                                     null                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Root of BST                       
                                                 let root=                                     null                                     ;                       
                                                 let succ=                                     null                                     ;                       
                                   
                                                 // A utility function to insert a new node with                       
                                                 // given data in BST and find its successor                       
                                                 function                                     insert(node,data)                       
                                                 {                       
                                                 // If the tree is empty, return a new node                       
                                                 if                                     (node ==                                     null                                     )                       
                                                 {                       
                                                 node =                                     new                                     Node(data);                       
                                                 }                       
                                   
                                                 // If key is smaller than root's key,                       
                                                 // go to left subtree and set successor                       
                                                 // as current node                       
                                                 if                                     (data < node.data)                       
                                                 {                       
                                                 succ = node;                       
                                                 node.left = insert(node.left, data);                       
                                                 }                       
                                   
                                                 // Go to right subtree                       
                                                 else                                     if                                     (data > node.data)                       
                                                 node.right = insert(node.right, data);                       
                                   
                                                 return                                     node;                       
                                                 }                       
                                   
                                                 // Function to replace every element with the                       
                                                 // least greater element on its right                       
                                                 function                                     replace(arr,n)                       
                                                 {                       
                                                 // start from right to left                       
                                                 for                                     (let i = n - 1; i >= 0; i--)                       
                                                 {                       
                                                 succ =                                     null                                     ;                       
                                   
                                                 // Insert current element into BST and                       
                                                 // find its inorder successor                       
                                                 root = insert(root, arr[i]);                       
                                   
                                                 // Replace element by its inorder                       
                                                 // successor in BST                       
                                                 if                                     (succ !=                                     null                                     )                       
                                                 arr[i] = succ.data;                       
                                   
                                                 // No inorder successor                       
                                                 else                       
                                                 arr[i] = -1;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 let arr=[8, 58, 71, 18, 31,                       
                                                 32, 63, 92, 43, 3,                       
                                                 91, 93, 25, 80, 28 ];                       
                                                 let n = arr.length;                       
                                                 replace(arr, n);                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                   
           
                         // This code is contributed by unknown2108                       
           
                         </script>                       

输出

18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1

这个 最坏情况下的时间复杂度 上述溶液的分子量也是O（n） ^2. )当数组按升序或降序排序时，最坏的情况就会发生。通过使用像红黑树这样的平衡树，可以很容易地将复杂度降低到O（nlogn）。

另一种方法：

我们可以使用 使用堆栈的下一个更大元素 算法为了解决这个问题 O（Nlog（N）） 时间和 O（N） 空间

算法：

首先，我们获取一个成对数组，即temp，并将每个元素及其索引存储在此数组中，即。 temp[i]将存储{arr[i]，i} .

对数组排序 根据数组元素。

现在为数组中临时数组的每个索引获取下一个更大的索引，即使用 下一个更大的元素 使用堆栈。

现在索引[i]存储元素temp[i]中下一个最小元素的索引。首先，如果索引[i]是-1，那么这意味着元素temp[i]中没有更大的元素。第二个在右边。

现在取一个结果数组，其中结果[i]将等于 a[index[temp[i]。第二]] 如果索引[i]不是-1，否则结果[i]将等于-1。

下面是上述方法的实现

C++

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         // function to get the next least greater index for each and                       
                         // every temp.second of the temp array using stack this                       
                         // function is similar to the Next Greater element for each                       
                         // and every element of an array using stack difference is                       
                         // we are finding the next greater index not value and the                       
                         // indexes are stored in the temp[i].second for all i                       
                         vector<                                     int                                     > nextGreaterIndex(vector<pair<                                     int                                     ,                                     int                                     > >& temp)                       
                         {                       
                                                 int                                     n = temp.size();                       
                                                 // initially result[i] for all i is -1                       
                                                 vector<                                     int                                     > res(n, -1);                       
                                                 stack<                                     int                                     > stack;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 // if the stack is empty or this index is smaller                       
                                                 // than the index stored at top of the stack then we                       
                                                 // push this index to the stack                       
                                                 if                                     (stack.empty() || temp[i].second < stack.top())                       
                                                 stack.push(                       
                                                 temp[i].second);                                     // notice temp[i].second is                       
                                                 // the index                       
                                                 // else this index (i.e. temp[i].second) is greater                       
                                                 // than the index stored at top of the stack we pop                       
                                                 // all the indexes stored at stack's top and for all                       
                                                 // these indexes we make this index i.e.                       
                                                 // temp[i].second as their next greater index                       
                                                 else                                     {                       
                                                 while                                     (!stack.empty()                       
                                                 && temp[i].second > stack.top()) {                       
                                                 res[stack.top()] = temp[i].second;                       
                                                 stack.pop();                       
                                                 }                       
                                                 // after that push the current index to the stack                       
                                                 stack.push(temp[i].second);                       
                                                 }                       
                                                 }                       
                                                 // now res will store the next least greater indexes for                       
                                                 // each and every indexes stored at temp[i].second for                       
                                                 // all i                       
                                                 return                                     res;                       
                         }                       
                         // now we will be using above function for finding the next                       
                         // greater index for each and every indexes stored at                       
                         // temp[i].second                       
                         vector<                                     int                                     > replaceByLeastGreaterUsingStack(                                     int                                     arr[],                       
                                                 int                                     n)                       
                         {                       
                                                 // first of all in temp we store the pairs of {arr[i].i}                       
                                                 vector<pair<                                     int                                     ,                                     int                                     > > temp;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 temp.push_back({ arr[i], i });                       
                                                 }                       
                                                 // we sort the temp according to the first of the pair                       
                                                 // i.e value                       
                                                 sort(temp.begin(), temp.end());                       
                                                 // now indexes vector will store the next greater index                       
                                                 // for each temp[i].second index                       
                                                 vector<                                     int                                     > indexes = nextGreaterIndex(temp);                       
                                                 // we initialize a result vector with all -1                       
                                                 vector<                                     int                                     > res(n, -1);                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 // now if there is no next greater index after the                       
                                                 // index temp[i].second the result will be -1                       
                                                 // otherwise the result will be the element of the                       
                                                 // array arr at index indexes[temp[i].second]                       
                                                 if                                     (indexes[temp[i].second] != -1)                       
                                                 res[temp[i].second]                       
                                                 = arr[indexes[temp[i].second]];                       
                                                 }                       
                                                 // return the res which will store the least greater                       
                                                 // element of each and every element in the array at its                       
                                                 // right side                       
                                                 return                                     res;                       
                         }                       
                         // driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 8,  58, 71, 18, 31, 32, 63, 92,                       
                                                 43, 3,  91, 93, 25, 80, 28 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (                                     int                                     );                       
                                                 auto                                     res = replaceByLeastGreaterUsingStack(arr, n);                       
                                                 cout <<                                     "Least Greater elements on the right side are "                       
                                                 << endl;                       
                                                 for                                     (                                     int                                     i : res)                       
                                                 cout << i <<                                     ' '                                     ;                       
                                                 cout << endl;                       
                                                 return                                     0;                       
                         }                                     // this code is contributed by Dipti Prakash Sinha                       

输出

Least Greater elements on the right side are 18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1

使用set的另一种方法

思考这个问题的另一种方式是列出我们的需求，然后仔细考虑，找到解决方案。如果我们向后遍历阵列，我们需要一个数据结构（ds）来支持：

1.按排序顺序将一个元素插入ds（因此在任何时间点，ds中的元素都会被排序）

2.找到当前元素的上界（如果存在，上界将给出ds中更大的元素）

仔细观察我们的要求，我们会想到一套。

为什么不多集呢？我们可以使用multiset，但不需要多次存储元素。

让我们为我们的方法编写代码

时空复杂性 ：我们在集合中插入每个元素，并使用循环找到每个元素的上界，使其时间复杂度为O（n*log（n））。我们在集合中存储每个元素，所以空间复杂度为O（n）

C++

                         #include <iostream>                       
                         #include <vector>                       
                         #include <set>                       
           
                         using                                     namespace                                     std;                       
           
                         void                                     solve(vector<                                     int                                     >& arr) {                       
                                                 set<                                     int                                     > s;                       
                                                 vector<                                     int                                     > ans(arr.size());                       
                                                 for                                     (                                     int                                     i=arr.size()-1;i>=0;i--) {                                     //traversing the array backwards                       
                                                 s.insert(arr[i]);                                     // inserting the element into set                       
                                                 auto                                     it = s.upper_bound(arr[i]);                                     // finding upper bound                       
                                                 if                                     (it == s.end()) arr[i] = -1;                                     // if upper_bound does not exist then -1                       
                                                 else                                     arr[i] = *it;                                     // if upper_bound exists, lets take it                       
                                                 }                       
                         }                       
           
                         void                                     printArray(vector<                                     int                                     >& arr) {                       
                                                 for                                     (                                     int                                     i : arr) cout << i <<                                     " "                                     ;                       
                                                 cout <<                                     ""                                     ;                       
                         }                       
           
                         int                                     main() {                       
                                                 vector<                                     int                                     > arr = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};                       
                                                 printArray(arr);                       
                                                 solve(arr);                       
                                                 printArray(arr);                       
                                                 return                                     0;                       
                         }                       

输出

8 58 71 18 31 32 63 92 43 3 91 93 25 80 28 18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1

本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章