Ņemot vērā veselu skaitļu masīvu, atrodiet nākamais mazāks no nākamais lielākais elements katram masīva elementam.
Piezīme : Elementi, kuriem nepastāv lielāks elements vai nav mazāks no lielāka elementa, drukāt -1.
Piemēri:
Input : arr[] = {5 1 9 2 5 1 7} Output: 2 2 -1 1 -1 -1 -1 Explanation : Next Greater -> Right Smaller 5 -> 9 9 -> 2 1 -> 9 9 -> 2 9 -> -1 -1 -> -1 2 -> 5 5 -> 1 5 -> 7 7 -> -1 1 -> 7 7 -> -1 7 -> -1 -1 -> -1 Input : arr[] = {4 8 2 1 9 5 6 3} Output : 2 5 5 5 -1 3 -1 -1 A vienkāršs risinājums ir atkārtot visus elementus. Katram elementam atrodiet nākamo lielāko pašreizējā elementa elementu un pēc tam atrodiet pareizo mazāko elementu pašreizējam nākamajam lielākajam elementam.
Kods-
C++// C++ Program to find Right smaller element of next // greater element #include
// Java Program to find Right smaller element of next // greater element import java.util.*; public class Main { // Function to find Right smaller element of next greater element static void nextSmallerOfNextGreater(int arr[] int n) { ArrayList<Integer> vec = new ArrayList<Integer>(); // For 1st n-1 elements of vector for(int i = 0; i < n - 1; i++) { int temp = arr[i]; int next = -1; int ans = -1; for(int j = i + 1; j < n; j++) { if(arr[j] > temp) { next = j; break; } } if(next == -1) { vec.add(-1); } else { for(int j = next + 1; j < n; j++) { if(arr[j] < arr[next]) { ans = j; break; } } if(ans == -1) { vec.add(-1); } else { vec.add(arr[ans]); } } } vec.add(-1); // For last element of vector for(int x : vec) { System.out.print(x + ' '); } System.out.println(); } // Driver program public static void main(String[] args) { int arr[] = {5 1 9 2 5 1 7}; int n = arr.length; nextSmallerOfNextGreater(arr n); } }
# Function to find Right smaller element of next greater element def nextSmallerOfNextGreater(arr n): vec = [] # For 1st n-1 elements of vector for i in range(n-1): temp = arr[i] next = -1 ans = -1 for j in range(i+1 n): if arr[j] > temp: next = j break if next == -1: vec.append(-1) else: for j in range(next+1 n): if arr[j] < arr[next]: ans = j break if ans == -1: vec.append(-1) else: vec.append(arr[ans]) vec.append(-1) # For last element of vector for x in vec: print(x end=' ') print() # Driver program arr = [5 1 9 2 5 1 7] n = len(arr) nextSmallerOfNextGreater(arr n)
using System; using System.Collections.Generic; public class MainClass { // Function to find Right smaller element of next // greater element static void nextSmallerOfNextGreater(int[] arr int n) { List<int> vec = new List<int>(); // For 1st n-1 elements of vector for (int i = 0; i < n - 1; i++) { int temp = arr[i]; int next = -1; int ans = -1; for (int j = i + 1; j < n; j++) { if (arr[j] > temp) { next = j; break; } } if (next == -1) { vec.Add(-1); } else { for (int j = next + 1; j < n; j++) { if (arr[j] < arr[next]) { ans = j; break; } } if (ans == -1) { vec.Add(-1); } else { vec.Add(arr[ans]); } } } vec.Add(-1); // For last element of vector foreach(var x in vec) { Console.Write(x + ' '); } Console.WriteLine(); } // Driver program public static void Main() { int[] arr = { 5 1 9 2 5 1 7 }; int n = arr.Length; nextSmallerOfNextGreater(arr n); } }
// Function to find Right smaller element of next greater element function nextSmallerOfNextGreater(arr n) { let vec = []; // For 1st n-1 elements of vector for (let i = 0; i < n - 1; i++) { let temp = arr[i]; let next = -1; let ans = -1; for (let j = i + 1; j < n; j++) { if (arr[j] > temp) { next = j; break; } } if (next == -1) { vec.push(-1); } else { for (let j = next + 1; j < n; j++) { if (arr[j] < arr[next]) { ans = j; break; } } if (ans == -1) { vec.push(-1); } else { vec.push(arr[ans]); } } } vec.push(-1); // For last element of vector for (let x of vec) { process.stdout.write(x + ' '); } console.log(); } // Driver program let arr = [5 1 9 2 5 1 7]; let n = arr.length; nextSmallerOfNextGreater(arr n);
Izvade
2 2 -1 1 -1 -1 -1
Laika sarežģītība no šī risinājuma ir O (n2).
Kosmosa sarežģītība: O(1)
An efektīvs risinājums aizņem O(n) laiku. Ievērojiet, ka tā ir kombinācija Nākamais lielākais elements & nākamais mazākais elements masīvā.
Let input array be 'arr[]' and size of array be 'n' find next greatest element of every element step 1 : Create an empty stack (S) in which we store the indexes and NG[] that is user to store the indexes of NGE of every element. step 2 : Traverse the array in reverse order where i goes from (n-1 to 0) a) While S is non empty and the top element of S is smaller than or equal to 'arr[i]': pop S b) If S is empty arr[i] has no greater element NG[i] = -1 c) else we have next greater element NG[i] = S.top() // here we store the index of NGE d) push current element index in stack S.push(i) Find Right smaller element of every element step 3 : create an array RS[] used to store the index of right smallest element step 4 : we repeat step (1 & 2) with little bit of modification in step 1 & 2 . they are : a). we use RS[] in place of NG[]. b). In step (2.a) we pop element form stack S while S is not empty or the top element of S is greater than or equal to 'arr[i]' step 5 : compute all RSE of NGE : where i goes from 0 to n-1 if NG[ i ] != -1 && RS[ NG [ i]] ! =-1 print arr[RS[NG[i]]] else print -1
Zemāk ir iepriekš minētās idejas īstenošana
C++// C++ Program to find Right smaller element of next // greater element #include
// Java Program to find Right smaller element of next // greater element import java.util.Stack; public class Main { // function find Next greater element public static void nextGreater(int arr[] int next[] char order) { // create empty stack Stack<Integer> stack=new Stack<>(); // Traverse all array elements in reverse order // order == 'G' we compute next greater elements of // every element // order == 'S' we compute right smaller element of // every element for (int i=arr.length-1; i>=0; i--) { // Keep removing top element from S while the top // element is smaller than or equal to arr[i] (if Key is G) // element is greater than or equal to arr[i] (if order is S) while (!stack.isEmpty() && ((order=='G')? arr[stack.peek()] <= arr[i]:arr[stack.peek()] >= arr[i])) stack.pop(); // store the next greater element of current element if (!stack.isEmpty()) next[i] = stack.peek(); // If all elements in S were smaller than arr[i] else next[i] = -1; // Push this element stack.push(i); } } // Function to find Right smaller element of next greater // element public static void nextSmallerOfNextGreater(int arr[]) { int NG[]=new int[arr.length]; // stores indexes of next greater elements int RS[]=new int[arr.length]; // stores indexes of right smaller elements // Find next greater element // Here G indicate next greater element nextGreater(arr NG 'G'); // Find right smaller element // using same function nextGreater() // Here S indicate right smaller elements nextGreater(arr RS 'S'); // If NG[i] == -1 then there is no smaller element // on right side. We can find Right smaller of next // greater by arr[RS[NG[i]]] for (int i=0; i< arr.length; i++) { if (NG[i] != -1 && RS[NG[i]] != -1) System.out.print(arr[RS[NG[i]]]+' '); else System.out.print('-1 '); } } public static void main(String args[]) { int arr[] = {5 1 9 2 5 1 7}; nextSmallerOfNextGreater(arr); } } //This code is contributed by Gaurav Tiwari
# Python 3 Program to find Right smaller element of next # greater element # function find Next greater element def nextGreater(arr n next order): S = [] # Traverse all array elements in reverse order # order == 'G' we compute next greater elements of # every element # order == 'S' we compute right smaller element of # every element for i in range(n-1-1-1): # Keep removing top element from S while the top # element is smaller than or equal to arr[i] (if Key is G) # element is greater than or equal to arr[i] (if order is S) while (S!=[] and (arr[S[len(S)-1]] <= arr[i] if (order=='G') else arr[S[len(S)-1]] >= arr[i] )): S.pop() # store the next greater element of current element if (S!=[]): next[i] = S[len(S)-1] # If all elements in S were smaller than arr[i] else: next[i] = -1 # Push this element S.append(i) # Function to find Right smaller element of next greater # element def nextSmallerOfNextGreater(arr n): NG = [None]*n # stores indexes of next greater elements RS = [None]*n # stores indexes of right smaller elements # Find next greater element # Here G indicate next greater element nextGreater(arr n NG 'G') # Find right smaller element # using same function nextGreater() # Here S indicate right smaller elements nextGreater(arr n RS 'S') # If NG[i] == -1 then there is no smaller element # on right side. We can find Right smaller of next # greater by arr[RS[NG[i]]] for i in range(n): if (NG[i] != -1 and RS[NG[i]] != -1): print(arr[RS[NG[i]]]end=' ') else: print('-1'end=' ') # Driver program if __name__=='__main__': arr = [5 1 9 2 5 1 7] n = len(arr) nextSmallerOfNextGreater(arr n) # this code is contributed by ChitraNayal
using System; using System.Collections.Generic; // C# Program to find Right smaller element of next // greater element public class GFG { // function find Next greater element public static void nextGreater(int []arr int []next char order) { // create empty stack Stack<int> stack=new Stack<int>(); // Traverse all array elements in reverse order // order == 'G' we compute next greater elements of // every element // order == 'S' we compute right smaller element of // every element for (int i=arr.Length-1; i>=0; i--) { // Keep removing top element from S while the top // element is smaller than or equal to arr[i] (if Key is G) // element is greater than or equal to arr[i] (if order is S) while (stack.Count!=0 && ((order=='G')? arr[stack.Peek()] <= arr[i]:arr[stack.Peek()] >= arr[i])) stack.Pop(); // store the next greater element of current element if (stack.Count!=0) next[i] = stack.Peek(); // If all elements in S were smaller than arr[i] else next[i] = -1; // Push this element stack.Push(i); } } // Function to find Right smaller element of next greater // element public static void nextSmallerOfNextGreater(int []arr) { int []NG=new int[arr.Length]; // stores indexes of next greater elements int []RS=new int[arr.Length]; // stores indexes of right smaller elements // Find next greater element // Here G indicate next greater element nextGreater(arr NG 'G'); // Find right smaller element // using same function nextGreater() // Here S indicate right smaller elements nextGreater(arr RS 'S'); // If NG[i] == -1 then there is no smaller element // on right side. We can find Right smaller of next // greater by arr[RS[NG[i]]] for (int i=0; i< arr.Length; i++) { if (NG[i] != -1 && RS[NG[i]] != -1) Console.Write(arr[RS[NG[i]]]+' '); else Console.Write('-1 '); } } public static void Main() { int []arr = {5 1 9 2 5 1 7}; nextSmallerOfNextGreater(arr); } } // This code is contributed by PrinciRaj1992
<script> // Javascript Program to find Right smaller element of next // greater element // function find Next greater element function nextGreater(arrnextorder) { // create empty stack let stack = []; // Traverse all array elements in reverse order // order == 'G' we compute next greater elements of // every element // order == 'S' we compute right smaller element of // every element for (let i = arr.length - 1; i >= 0; i--) { // Keep removing top element from S while the top // element is smaller than or equal to arr[i] (if Key is G) // element is greater than or equal to arr[i] (if order is S) while (stack.length!=0 && ((order=='G')? arr[stack[stack.length-1]] <= arr[i] : arr[stack[stack.length-1]] >= arr[i])) stack.pop(); // store the next greater element of current element if (stack.length != 0) next[i] = stack[stack.length - 1]; // If all elements in S were smaller than arr[i] else next[i] = -1; // Push this element stack.push(i); } } // Function to find Right smaller element of next greater // element function nextSmallerOfNextGreater(arr) { let NG = new Array(arr.length); // stores indexes of next greater elements let RS = new Array(arr.length); // stores indexes of right smaller elements for(let i = 0; i < arr.length; i++) { NG[i] = 0; RS[i] = 0; } // Find next greater element // Here G indicate next greater element nextGreater(arr NG 'G'); // Find right smaller element // using same function nextGreater() // Here S indicate right smaller elements nextGreater(arr RS 'S'); // If NG[i] == -1 then there is no smaller element // on right side. We can find Right smaller of next // greater by arr[RS[NG[i]]] for (let i = 0; i < arr.length; i++) { if (NG[i] != -1 && RS[NG[i]] != -1) document.write(arr[RS[NG[i]]] + ' '); else document.write('-1 '); } } // Driver code let arr = [5 1 9 2 5 1 7]; nextSmallerOfNextGreater(arr); // This code is contributed by rag2127 </script>
Izvade
2 2 -1 1 -1 -1 -1
Laika sarežģītība: O(n) kur n ir dotā masīva lielums.
Palīgtelpa: O(n ) kur n ir dotā masīva lielums.
Izveidojiet viktorīnu