Dada una array arr[] , la tarea es contar el número de tripletes tales que i < j <k y a[ j ]< a[ k ]< a[ i ] .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: -1
Explicación: No hay tripletes del tipo requerido.Entrada: arr[] = {4, 1, 3, 5}
Salida: 1
Explicación: Hay un triplete en el arreglo a[]: {4, 1, 3}.Entrada: arr[] = {2, 1, -3, -2, 5}
Salida: 2
Explicación: Hay dos tripletas de tipo requerido: {2, 1, -3}, {1, -3, -2}
Enfoque ingenuo: use tres bucles para verificar todos los tripletes posibles en a[] y cuente el número de tripletes en arr[] de modo que i<j<k y a[ j ]< a[ k ]< a[ i ]. A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
int findTriplets(int a[], int n)
{
// To count desired triplets
int cnt = 0;
// Three loops to find triplets
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int k = j + 1; k < n; k++)
{
if (a[j] < a[k] && a[k] < a[i])
cnt++;
}
}
}
// Return the number of triplets found
return cnt;
}
// Driver code
int main()
{
int a[] = {2, 1, -3, -2, 5};
int n = sizeof(a) / sizeof(a[0]);
cout << (findTriplets(a, n));
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java Program for above approach
import java.io.*;
class GFG {
public static int findTriplets(int[] a)
{
// To count desired triplets
int cnt = 0;
// Three loops to find triplets
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
for (int k = j + 1; k < a.length; k++) {
if (a[j] < a[k] && a[k] < a[i])
cnt++;
}
}
}
// Return the number of triplets found
return cnt;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 1, -3, -2, 5 };
System.out.println(findTriplets(a));
}
}
Python3
# Python Program for above approach def findTriplets(a): # To count desired triplets cnt = 0; # Three loops to find triplets for i in range(len(a)): for j in range(i + 1, len(a)): for k in range(j + 1, len(a)): if (a[j] < a[k] and a[k] < a[i]): cnt += 1 # Return the number of triplets found return cnt; # Driver code a = [2, 1, -3, -2, 5]; print(findTriplets(a)); # This code is contributed by Saurabh Jaiswal
C#
// C# Program for above approach
using System;
public class GFG {
public static int findTriplets(int[] a)
{
// To count desired triplets
int cnt = 0;
// Three loops to find triplets
for (int i = 0; i < a.Length; i++) {
for (int j = i + 1; j < a.Length; j++) {
for (int k = j + 1; k < a.Length; k++) {
if (a[j] < a[k] && a[k] < a[i])
cnt++;
}
}
}
// Return the number of triplets found
return cnt;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 2, 1, -3, -2, 5 };
Console.WriteLine(findTriplets(a));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program for above approach
function findTriplets(a) {
// To count desired triplets
let cnt = 0;
// Three loops to find triplets
for (let i = 0; i < a.length; i++) {
for (let j = i + 1; j < a.length; j++) {
for (let k = j + 1; k < a.length; k++) {
if (a[j] < a[k] && a[k] < a[i])
cnt++;
}
}
}
// Return the number of triplets found
return cnt;
}
// Driver code
let a = [2, 1, -3, -2, 5];
document.write(findTriplets(a));
// This code is contributed by gfgking.
</script>
Producción
2
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: se puede usar una pila para optimizar la solución anterior. La pila hará un seguimiento del siguiente elemento más pequeño y del segundo elemento más pequeño del lado derecho.
Siga los pasos a continuación para resolver el problema dado.
- Cree una pila y una variable, digamos secondMin = INT_MAX .
- Declare una variable, digamos cnt = 0 , para almacenar el número de tripletes deseados.
- Comience a atravesar desde el final de la array a[] .
- Verifique si el elemento actual es mayor que el segundo Min , si es eso significa que se encontró el triplete requerido porque la pila realiza un seguimiento de los siguientes elementos más pequeños y el segundo más pequeño y el elemento actual satisface el tipo. Luego, establece cnt = cnt + 1 .
- Si la condición anterior no se cumple, actualice el valor mínimo en la pila , siga saltando hasta que la pila no esté vacía o el elemento actual no sea más pequeño que la parte superior de la pila .
- Empuje el elemento actual en la pila
- Por último, devuelva cnt como el número de tripletes encontrados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find desired triplets
int findTriplets(vector<int>& a)
{
// To store the number of triplets found
int cnt = 0;
stack<int> st;
// Keep track of second minimum element
int secondMin = INT_MAX;
for (int i = a.size() - 1; i >= 0; i--) {
// If required triplet is found
if (a[i] > secondMin)
cnt++;
while (!st.empty() && st.top() > a[i]) {
secondMin = st.top();
st.pop();
}
st.push(a[i]);
}
// Return the number of triplets found
return cnt;
}
// Driver code
int main()
{
vector<int> a = { 2, 1, -3, -2, 5 };
// Print the required result
cout << findTriplets(a);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java program for above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find desired triplets
public static int findTriplets(int[] a)
{
// To store the number of triplets found
int cnt = 0;
Stack<Integer> stack = new Stack<>();
// Keep track of second minimum element
int secondMin = Integer.MAX_VALUE;
for (int i = a.length - 1; i >= 0; i--) {
// If required triplet is found
if (a[i] > secondMin)
cnt++;
while (!stack.isEmpty()
&& stack.peek() > a[i]) {
secondMin = stack.pop();
}
stack.push(a[i]);
}
// Return the number of triplets found
return cnt;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 1, -3, -2, 5 };
// Print the required result
System.out.println(findTriplets(a));
}
}
Python3
# Python 3 program for above approach import sys # Function to find desired triplets def findTriplets(a): # To store the number of triplets found cnt = 0 st = [] # Keep track of second minimum element secondMin = sys.maxsize for i in range(len(a) - 1, -1, -1): # If required triplet is found if (a[i] > secondMin): cnt += 1 while (not len(st) == 0 and st[-1] > a[i]): secondMin = st[-1] st.pop() st.append(a[i]) # Return the number of triplets found return cnt # Driver code if __name__ == "__main__": a = [2, 1, -3, -2, 5] # Print the required result print(findTriplets(a)) # This code is contributed by ukasp.
C#
// C# program for above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to find desired triplets
public static int findTriplets(int[] a)
{
// To store the number of triplets found
int cnt = 0;
Stack<int> stack = new Stack<int>();
// Keep track of second minimum element
int secondMin = int.MaxValue;
for (int i = a.Length - 1; i >= 0; i--) {
// If required triplet is found
if (a[i] > secondMin)
cnt++;
while (stack.Count!=0
&& stack.Peek() > a[i]) {
secondMin = stack.Pop();
}
stack.Push(a[i]);
}
// Return the number of triplets found
return cnt;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 2, 1, -3, -2, 5 };
// Print the required result
Console.WriteLine(findTriplets(a));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript program for above approach
// Function to find desired triplets
function findTriplets(a)
{
// To store the number of triplets found
var cnt = 0;
var stack = [];
// Keep track of second minimum element
var secondMin = Number.MAX_VALUE;
for (var i = a.length - 1; i >= 0; i--) {
// If required triplet is found
if (a[i] > secondMin)
cnt++;
while (stack.length!=0
&& stack[0] > a[i]) {
secondMin = stack.pop();
}
stack.push(a[i]);
}
// Return the number of triplets found
return cnt;
}
// Driver code
var a = [ 2, 1, -3, -2, 5 ];
// Print the required result
document.write(findTriplets(a));
// This code is contributed by shikhasingrajput
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por iramkhalid24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA