Dado un arreglo arr[] , la tarea es encontrar el triplete lexicográficamente más grande en ese arreglo que pueda formar un triángulo. Si no existe tal triplete, imprima -1 .
Ejemplo:
Entrada: arr[] = { 4, 2, 10, 3, 5 }
Salida: 3 4 5
Explicación:
El triplete lexicográficamente más grande es (4, 5, 10). Pero no forma un triángulo.
El siguiente triplete lexicográficamente más grande es (3, 4, 5).
Como forma un triángulo, es la respuesta requerida.
Entrada: arr[] = { 20, 12, 120, 3, 15 }
Salida: 12 15 20
Enfoque:
Un triplete puede formar un triángulo si y solo si sigue la condición dada a continuación:
Si A, B y C forman un triplete, entonces el triplete puede formar un triángulo si
A < B + C o B < A + C o C < A + B
La idea es usar Sorting . Ordene la array en orden ascendente. Comience a atravesar desde el final de la array y verifique si algún triplete satisface la condición anterior. Imprima el primer triplete para satisfacer la condición, como salida. Si no se puede encontrar tal triplete, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find lexicographically // largest triplet that forms a // triangle in the given array void findTriplet(int arr[], int N) { // Sort the array sort(arr, arr + N); int flag = 0, i; // Iterate from the end of the array for (i = N - 1; i - 2 >= 0; i--) { // If the triplet forms a triangle if (arr[i - 2] + arr[i - 1] > arr[i]) { flag = 1; break; } } // If triplet found if (flag) { // Print the triplet cout << arr[i - 2] << " " << arr[i - 1] << " " << arr[i] << endl; } // Otherwise else { cout << -1 << endl; } } // Driver Code int main() { int arr[] = { 4, 2, 10, 3, 5 }; int N = sizeof(arr) / sizeof(arr[0]); findTriplet(arr, N); return 0; }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find lexicographically // largest triplet that forms a // triangle in the given array static void findTriplet(int arr[], int N) { // Sort the array Arrays.sort(arr); int flag = 0, i; // Iterate from the end of the array for(i = N - 1; i - 2 >= 0; i--) { // If the triplet forms a triangle if (arr[i - 2] + arr[i - 1] > arr[i]) { flag = 1; break; } } // If triplet found if (flag != 0) { // Print the triplet System.out.println(arr[i - 2] + " " + arr[i - 1] + " " + arr[i] ); } // Otherwise else { System.out.println(-1); } } // Driver Code public static void main (String []args) { int arr[] = { 4, 2, 10, 3, 5 }; int N = arr.length; findTriplet(arr, N); } } // This code is contributed by chitranayal
Python3
# Python3 implementation of # the above approach # Function to find lexicographically # largest triplet that forms a # triangle in the given array def findTriplet(arr, N): # Sort the array arr.sort() # Iterate from the end of the array i = N - 1 while i - 2 >= 0: # If the triplet forms a triangle if(arr[i - 2] + arr[i - 1] > arr[i]): flag = 1 break i -= 1 # If triplet found if(flag): # Print the triplet print(arr[i - 2], arr[i - 1], arr[i]) # Otherwise else: print(-1) # Driver Code if __name__ == '__main__': arr = [ 4, 2, 10, 3, 5 ] N = len(arr) findTriplet(arr, N) # This code is contributed by Shivam Singh
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find lexicographically // largest triplet that forms a // triangle in the given array static void findTriplet(int []arr, int N) { // Sort the array Array.Sort(arr); int flag = 0, i; // Iterate from the end of the array for(i = N - 1; i - 2 >= 0; i--) { // If the triplet forms a triangle if (arr[i - 2] + arr[i - 1] > arr[i]) { flag = 1; break; } } // If triplet found if (flag != 0) { // Print the triplet Console.Write(arr[i - 2] + " " + arr[i - 1] + " " + arr[i] ); } // Otherwise else { Console.Write(-1); } } // Driver Code public static void Main (string []args) { int []arr = { 4, 2, 10, 3, 5 }; int N = arr.Length; findTriplet(arr, N); } } // This code is contributed by Ritik Bansal
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find lexicographically // largest triplet that forms a // triangle in the given array function findTriplet(arr, N) { // Sort the array arr.sort((a, b) => a - b); var flag = 0, i; // Iterate from the end of the array for (i = N - 1; i - 2 >= 0; i--) { // If the triplet forms a triangle if (arr[i - 2] + arr[i - 1] > arr[i]) { flag = 1; break; } } // If triplet found if (flag) { // Print the triplet document.write( arr[i - 2] + " " + arr[i - 1] + " " + arr[i] + "<br>" ); } // Otherwise else { document.write(-1 + "<br>"); } } // Driver Code var arr = [4, 2, 10, 3, 5]; var N = arr.length; findTriplet(arr, N); </script>
3 4 5
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA