Dada una array arr[] , la tarea es verificar que si existe un triplete (i, j, k) tal que arr[i]<arr[k]<arr[j] e i<j<k entonces imprima Sí de lo contrario imprima No.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: No
Explicación:
No existe tal subsecuencia tal que arr[i] < arr[k] < arr[j]Entrada: arr[] = {3, 1, 5, 0, 4}
Salida: Sí
Explicación:
Existe un triplete (3, 5, 4) que es arr[i] < arr[k] < arr[j]
Enfoque ingenuo: la idea es generar todos los tripletes posibles y, si alguno de los tripletes satisface las condiciones dadas, imprime Sí , de lo contrario, imprime No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] bool findTriplet(vector<int> nums) { for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { for (int k = j + 1; k < nums.size(); k++) { // Triplet found, hence return false if (nums[i] < nums[k] && nums[k] < nums[j]) return true; } } } // No triplet found, hence return false return false; } // Driver Code int main() { // Given array vector<int> arr = { 4, 7, 5, 6 }; // Function Call if (findTriplet(arr)) { cout << " Yes" << '\n'; } else { cout << " No" << '\n'; } return 0; }
Python3
# Python3 program for the above approach # Function to check if there exist # triplet in the array such that # i < j < k and arr[i] < arr[k] < arr[j] def findTriplet(nums): for i in range(len(nums)): for j in range(i + 1, len(nums)): for k in range(j + 1, len(nums)): # Triplet found, hence return false if(nums[i] < nums[k] and nums[k] < nums[j]): return True # No triplet found, hence return false return False # Driver Code # Given array arr = [ 4, 7, 5, 6 ] # Function Call if (findTriplet(arr)): print(" Yes") else: print(" No") # This code is contributed by shinjanpatra
Javascript
<script> // JavaScript program for the above approach // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] function findTriplet(nums) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { for (let k = j + 1; k < nums.length; k++) { // Triplet found, hence return false if (nums[i] < nums[k] && nums[k] < nums[j]) return true; } } } // No triplet found, hence return false return false; } // Driver Code // Given array let arr = [ 4, 7, 5, 6 ]; // Function Call if (findTriplet(arr)) { document.write(" Yes","</br>") } else { document.write(" No","</br>") } // This code is contributed by shinjanpatra </script>
C#
// C# program for the above approach using System; public class HelloWorld { // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] public static bool findTriplet(int[] nums) { for (int i = 0; i < nums.Length; i++) { for (int j = i + 1; j < nums.Length; j++) { for (int k = j + 1; k < nums.Length; k++) { // Triplet found, hence return false if (nums[i] < nums[k] && nums[k] < nums[j]) return true; } } } // No triplet found, hence return false return false; } public static void Main(string[] args) { // Given array int []arr = { 4, 7, 5, 6 }; // Function Call if (findTriplet(arr)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code is contributed by CodeWithMini
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] public static boolean findTriplet(int[] nums) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { for (int k = j + 1; k < nums.length; k++) { // Triplet found, hence return false if (nums[i] < nums[k] && nums[k] < nums[j]) return true; } } } // No triplet found, hence return false return false; } // Driver code public static void main(String[] args) { // Given array int arr[] = { 4, 7, 5, 6 }; // Function call if (findTriplet(arr)) { System.out.println("Yes"); } else { System.out.println("No"); } } } // This code is contributed by CodeWithMini
Producción:
Yes
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la pila para realizar un seguimiento de los elementos más pequeños a la derecha de cada elemento de la array arr[] . A continuación se muestran los pasos:
- Atraviese la array desde el final y mantenga una pila que almacene el elemento en orden decreciente.
- Para mantener la pila en orden decreciente, extraiga los elementos que son más pequeños que el elemento actual. Luego marque el elemento reventado como el tercer elemento del triplete.
- Mientras recorre la array en sentido inverso, si algún elemento es menor que el último elemento extraído (que está marcado como el tercer elemento del triplete). Entonces existe un triplete que satisface la condición dada e imprime Sí .
- De lo contrario , imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] bool findTriplet(vector<int>& arr) { int n = arr.size(); stack<int> st; // Initialize the heights of h1 and h2 // to INT_MAX and INT_MIN respectively int h3 = INT_MIN, h1 = INT_MAX; for (int i = n - 1; i >= 0; i--) { // Store the current element as h1 h1 = arr[i]; // If the element at top of stack // is less than the current element // then pop the stack top // and keep updating the value of h3 while (!st.empty() && st.top() < arr[i]) { h3 = st.top(); st.pop(); } // Push the current element // on the stack st.push(arr[i]); // If current element is less // than h3, then we found such // triplet and return true if (h1 < h3) { return true; } } // No triplet found, hence return false return false; } // Driver Code int main() { // Given array vector<int> arr = { 4, 7, 5, 6 }; // Function Call if (findTriplet(arr)) { cout << " Yes" << '\n'; } else { cout << " No" << '\n'; } return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] public static boolean findTriplet(int[] arr) { int n = arr.length; Stack<Integer> st = new Stack<>(); // Initialize the heights of h1 and h2 // to INT_MAX and INT_MIN respectively int h3 = Integer.MIN_VALUE; int h1 = Integer.MAX_VALUE; for(int i = n - 1; i >= 0; i--) { // Store the current element as h1 h1 = arr[i]; // If the element at top of stack // is less than the current element // then pop the stack top // and keep updating the value of h3 while (!st.empty() && st.peek() < arr[i]) { h3 = st.peek(); st.pop(); } // Push the current element // on the stack st.push(arr[i]); // If current element is less // than h3, then we found such // triplet and return true if (h1 < h3) { return true; } } // No triplet found, hence return false return false; } // Driver code public static void main(String[] args) { // Given array int arr[] = { 4, 7, 5, 6 }; // Function call if (findTriplet(arr)) { System.out.println("Yes"); } else { System.out.println("No"); } } } // This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach import sys # Function to check if there exist # triplet in the array such that # i < j < k and arr[i] < arr[k] < arr[j] def findTriplet(arr): n = len(arr) st = [] # Initialize the heights of h1 and h3 # to INT_MAX and INT_MIN respectively h3 = -sys.maxsize - 1 h1 = sys.maxsize for i in range(n - 1, -1, -1): # Store the current element as h1 h1 = arr[i] # If the element at top of stack # is less than the current element # then pop the stack top # and keep updating the value of h3 while (len(st) > 0 and st[-1] < arr[i]): h3 = st[-1] del st[-1] # Push the current element # on the stack st.append(arr[i]) # If current element is less # than h3, then we found such # triplet and return true if (h1 < h3): return True # No triplet found, hence # return false return False # Driver Code if __name__ == '__main__': # Given array arr = [ 4, 7, 5, 6 ] # Function Call if (findTriplet(arr)): print("Yes") else: print("No") # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] public static bool findTriplet(int[] arr) { int n = arr.Length; Stack<int> st = new Stack<int>(); // Initialize the heights of h1 and h2 // to INT_MAX and INT_MIN respectively int h3 = int.MinValue; int h1 = int.MaxValue; for(int i = n - 1; i >= 0; i--) { // Store the current element as h1 h1 = arr[i]; // If the element at top of stack // is less than the current element // then pop the stack top // and keep updating the value of h3 while (st.Count != 0 && st.Peek() < arr[i]) { h3 = st.Peek(); st.Pop(); } // Push the current element // on the stack st.Push(arr[i]); // If current element is less // than h3, then we found such // triplet and return true if (h1 < h3) { return true; } } // No triplet found, hence return false return false; } // Driver code public static void Main(String[] args) { // Given array int []arr = { 4, 7, 5, 6 }; // Function call if (findTriplet(arr)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript program for the above approach // Function to check if there exist // triplet in the array such that // i < j < k and arr[i] < arr[k] < arr[j] function findTriplet(arr) { var n = arr.length; var st = []; // Initialize the heights of h1 and h2 // to INT_MAX and INT_MIN respectively var h3 = -1000000000, h1 = 1000000000; for (var i = n - 1; i >= 0; i--) { // Store the current element as h1 h1 = arr[i]; // If the element at top of stack // is less than the current element // then pop the stack top // and keep updating the value of h3 while (st.length!=0 && st[st.length-1] < arr[i]) { h3 = st[st.length-1]; st.pop(); } // Push the current element // on the stack st.push(arr[i]); // If current element is less // than h3, then we found such // triplet and return true if (h1 < h3) { return true; } } // No triplet found, hence return false return false; } // Driver Code // Given array var arr = [4, 7, 5, 6 ]; // Function Call if (findTriplet(arr)) { document.write( " Yes"); } else { document.write( " No" ); } </script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mukulkumar10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA