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>
Producción:
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