Dada una array de n enteros, encuentre los 3 elementos tales que a[i] < a[j] < a[k] e i < j < k en 0(n) tiempo. Si hay varios de esos tripletes, imprima cualquiera de ellos.
Ejemplos:
Input: arr[] = {12, 11, 10, 5, 6, 2, 30}
Output: 5, 6, 30
Explanation: As 5 < 6 < 30, and they
appear in the same sequence in the array
Input: arr[] = {1, 2, 3, 4}
Output: 1, 2, 3 OR 1, 2, 4 OR 2, 3, 4
Explanation: As the array is sorted, for every i, j, k,
where i < j < k, arr[i] < arr[j] < arr[k]
Input: arr[] = {4, 3, 2, 1}
Output: No such triplet exists.
MÉTODO 1:
Sugerencia: utilice el espacio auxiliar.
Solución: Entonces, el motivo principal es encontrar un elemento que tenga un elemento más pequeño que él mismo en el lado izquierdo de la array y un elemento mayor que él mismo en el lado derecho de la array, si existe tal elemento, entonces existe un triplete que satisface los criterios.
Planteamiento: Esto se puede solucionar de una forma muy sencilla. Para encontrar un elemento que tiene un elemento más pequeño que él mismo en su lado izquierdo de la array, verifique si ese elemento es el elemento más pequeño mientras atraviesa la array desde el índice inicial, es decir, (0), y verifique si hay un elemento mayor que sí mismo en su lado derecho de la array, compruebe si ese elemento es el elemento más grande mientras se desplaza desde el final de la array, es decir, (n-1). Si el elemento no es el elemento más pequeño desde 0 hasta ese índice, entonces tiene un elemento más pequeño que él mismo en su lado izquierdo y, de manera similar, si el elemento no es el elemento más grande desde ese índice hasta el último índice, entonces hay un elemento más grande. en su lado derecho.
Algoritmo
- Cree una array auxiliar más pequeña [0..n-1]. small[i] almacena el índice de un número que es más pequeño que arr[i] y está en el lado izquierdo. La array contiene -1 si no existe tal elemento.
- Cree otra array auxiliar mayor [0..n-1]. mayor[i] almacena el índice de un número que es mayor que arr[i] y está en el lado derecho de arr[i]. La array contiene -1 si no existe tal elemento.
- Finalmente, recorra tanto el menor [] como el mayor [] y encuentre el índice [i] para el cual tanto el menor [i] como el mayor [i] no son iguales a -1.
C++
// C++ program to find a sorted
// sub-sequence of size 3
#include <bits/stdc++.h>
using namespace std;
// A function to fund a sorted
// sub-sequence of size 3
void find3Numbers(int arr[], int n)
{
// Index of maximum element
// from right side
int max = n - 1;
// Index of minimum element
// from left side
int min = 0;
int i;
// Create an array that will store
// index of a smaller element on left side.
// If there is no smaller element on left
// side, then smaller[i] will be -1.
int* smaller = new int[n];
// first entry will always be -1
smaller[0] = -1;
for (i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[i] = -1;
}
else
smaller[i] = min;
}
// Create another array that will
// store index of a greater element
// on right side. If there is no greater
// element on right side, then
// greater[i] will be -1.
int* greater = new int[n];
// last entry will always be -1
greater[n - 1] = -1;
for (i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[max]) {
max = i;
greater[i] = -1;
}
else
greater[i] = max;
}
// Now find a number which has both
// a greater number on right side and
// smaller number on left side
for (i = 0; i < n; i++) {
if (smaller[i] != -1 && greater[i] != -1) {
cout << arr[smaller[i]]
<< " " << arr[i] << " "
<< arr[greater[i]];
return;
}
}
// If we reach number, then there are
// no such 3 numbers
cout << "No such triplet found";
// Free the dynamically allocated memory
// to avoid memory leak
delete[] smaller;
delete[] greater;
return;
}
// Driver code
int main()
{
int arr[] = { 12, 11, 10, 5, 6, 2, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
find3Numbers(arr, n);
return 0;
a greater number on
}
// This is code is contributed by rathbhupendra
C
// C program to find a sorted
// sub-sequence of size 3
#include <stdio.h>
// A function to fund a sorted
// sub-sequence of size 3
void find3Numbers(int arr[], int n)
{
// Index of maximum element
// from right side
int max = n - 1;
// Index of minimum element
// from left side
int min = 0;
int i;
// Create an array that will store
// index of a smaller element on left side.
// If there is no smaller element on left side,
// then smaller[i] will be -1.
int* smaller = new int[n];
// first entry will always be -1
smaller[0] = -1;
for (i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[i] = -1;
}
else
smaller[i] = min;
}
// Create another array that will
// store index of a greater element
// on right side. If there is no greater
// element on right side, then
// greater[i] will be -1.
int* greater = new int[n];
// last entry will always be -1
greater[n - 1] = -1;
for (i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[max]) {
max = i;
greater[i] = -1;
}
else
greater[i] = max;
}
// Now find a number which has
// both a greater number on right
// side and smaller number on left side
for (i = 0; i < n; i++) {
if (smaller[i] != -1 && greater[i] != -1) {
printf("%d %d %d", arr[smaller[i]],
arr[i], arr[greater[i]]);
return;
}
}
// If we reach number, then
// there are no such 3 numbers
printf("No such triplet found");
// Free the dynamically allocated memory
// to avoid memory leak
delete[] smaller;
delete[] greater;
return;
}
// Driver program to test above function
int main()
{
int arr[] = { 12, 11, 10, 5, 6, 2, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
find3Numbers(arr, n);
return 0;
}
Java
// Java program to find a sorted
// sub-sequence of size 3
import java.io.*;
class SortedSubsequence {
// A function to find a sorted
// sub-sequence of size 3
static void find3Numbers(int arr[])
{
int n = arr.length;
// Index of maximum element
// from right side
int max = n - 1;
// Index of minimum element
// from left side
int min = 0;
int i;
// Create an array that will store
// index of a smaller element on left side.
// If there is no smaller element on left
// side, then smaller[i] will be -1.
int[] smaller = new int[n];
// first entry will always be -1
smaller[0] = -1;
for (i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[i] = -1;
}
else
smaller[i] = min;
}
// Create another array that will
// store index of a greater element
// on right side. If there is no greater
// element on right side, then greater[i]
// will be -1.
int[] greater = new int[n];
// last entry will always be -1
greater[n - 1] = -1;
for (i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[max]) {
max = i;
greater[i] = -1;
}
else
greater[i] = max;
}
// Now find a number which has
// both greater number on right
// side and smaller number on left side
for (i = 0; i < n; i++) {
if (
smaller[i] != -1 && greater[i] != -1) {
System.out.print(
arr[smaller[i]] + " " + arr[i]
+ " " + arr[greater[i]]);
return;
}
}
// If we reach number, then there
// are no such 3 numbers
System.out.println("No such triplet found");
return;
}
public static void main(String[] args)
{
int arr[] = { 12, 11, 10, 5, 6, 2, 30 };
find3Numbers(arr);
}
}
/* This code is contributed by Devesh Agrawal*/
Python
# Python program to fund a sorted # sub-sequence of size 3 def find3numbers(arr): n = len(arr) # Index of maximum element from right side max = n-1 # Index of minimum element from left side min = 0 # Create an array that will store # index of a smaller element on left side. # If there is no smaller element on left side, # then smaller[i] will be -1. smaller = [0]*10000 smaller[0] = -1 for i in range(1, n): if (arr[i] <= arr[min]): min = i smaller[i] = -1 else: smaller[i] = min # Create another array that will # store index of a greater element # on right side. If there is no greater # element on right side, then greater[i] # will be -1. greater = [0]*10000 greater[n-1] = -1 for i in range(n-2, -1, -1): if (arr[i] >= arr[max]): max = i greater[i] = -1 else: greater[i] = max # Now find a number which has # both a greater number on right # side and smaller number on left side for i in range(0, n): if smaller[i] != -1 and greater[i] != -1: print arr[smaller[i]], arr[i], arr[greater[i]] return # If we reach here, then there are no such 3 numbers print "No triplet found" return # Driver function to test above function arr = [12, 11, 10, 5, 6, 2, 30] find3numbers(arr) # This code is contributed by Devesh Agrawal
C#
// C# program to find a sorted
// subsequence of size 3
using System;
class SortedSubsequence {
// A function to find a sorted
// subsequence of size 3
static void find3Numbers(int[] arr)
{
int n = arr.Length;
// Index of maximum element from right side
int max = n - 1;
// Index of minimum element from left side
int min = 0;
int i;
// Create an array that will store index
// of a smaller element on left side.
// If there is no smaller element
// on left side, then smaller[i] will be -1.
int[] smaller = new int[n];
// first entry will always be -1
smaller[0] = -1;
for (i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[i] = -1;
}
else
smaller[i] = min;
}
// Create another array that will store
// index of a greater element on right side.
// If there is no greater element on
// right side, then greater[i] will be -1.
int[] greater = new int[n];
// last entry will always be -1
greater[n - 1] = -1;
for (i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[max]) {
max = i;
greater[i] = -1;
}
else
greater[i] = max;
}
// Now find a number which has
// both a greater number on right side
// and smaller number on left side
for (i = 0; i < n; i++) {
if (smaller[i] != -1 && greater[i] != -1) {
Console.Write(
arr[smaller[i]] + " " + arr[i]
+ " " + arr[greater[i]]);
return;
}
}
// If we reach number, then there
// are no such 3 numbers
Console.Write("No such triplet found");
return;
}
// Driver code
public static void Main()
{
int[] arr = { 12, 11, 10, 5, 6, 2, 30 };
find3Numbers(arr);
}
}
/* This code is contributed by vt_m*/
PHP
<?php
// PHP program to find a sorted
// subsequence of size 3
// A function to fund a sorted
// subsequence of size 3
function find3Numbers(&$arr, $n)
{
// Index of maximum element from right side
$max = $n - 1;
// Index of minimum element from left side
$min = 0;
// Create an array that will store
// index of a smaller element on
// left side. If there is no smaller
// element on left side, then
// smaller[i] will be -1.
$smaller = array_fill(0, $n, NULL);
$smaller[0] = -1; // first entry will
// always be -1
for ($i = 1; $i < $n; $i++)
{
if ($arr[$i] <= $arr[$min])
{
$min = $i;
$smaller[$i] = -1;
}
else
$smaller[$i] = $min;
}
// Create another array that will
// store index of a greater element
// on right side. If there is no
// greater element on right side,
// then greater[i] will be -1.
$greater = array_fill(0, $n, NULL);
// last entry will always be -1
$greater[$n - 1] = -1;
for ($i = $n - 2; $i >= 0; $i--)
{
if ($arr[$i] >= $arr[$max])
{
$max = $i;
$greater[$i] = -1;
}
else
$greater[$i] = $max;
}
// Now find a number which has both
// a greater number on right side
// and smaller number on left side
for ($i = 0; $i < $n; $i++)
{
if ($smaller[$i] != -1 &&
$greater[$i] != -1)
{
echo $arr[$smaller[$i]]." ".
$arr[$i] . " " .
$arr[$greater[$i]];
return;
}
}
// If we reach number, then there
// are no such 3 numbers
printf("No such triplet found");
return;
}
// Driver Code
$arr = array(12, 11, 10, 5, 6, 2, 30);
$n = sizeof($arr);
find3Numbers($arr, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find a sorted
// sub-sequence of size 3
// A function to find a sorted
// sub-sequence of size 3
function find3Numbers(arr)
{
let n = arr.length;
// Index of maximum element
// from right side
let max = n - 1;
// Index of minimum element
// from left side
let min = 0;
let i;
// Create an array that will store
// index of a smaller element on left side.
// If there is no smaller element on left
// side, then smaller[i] will be -1.
let smaller = new Array(n);
for(i=0;i<n;i++)
{
smaller[i]=0;
}
// first entry will always be -1
smaller[0] = -1;
for (i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[i] = -1;
}
else
smaller[i] = min;
}
// Create another array that will
// store index of a greater element
// on right side. If there is no greater
// element on right side, then greater[i]
// will be -1.
let greater = new Array(n);
for(i=0;i<n;i++)
{
greater[i]=0;
}
// last entry will always be -1
greater[n - 1] = -1;
for (i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[max]) {
max = i;
greater[i] = -1;
}
else
greater[i] = max;
}
// Now find a number which has
// both greater number on right
// side and smaller number on left side
for (i = 0; i < n; i++) {
if (
smaller[i] != -1 && greater[i] != -1) {
document.write(
arr[smaller[i]] + " " + arr[i]
+ " " + arr[greater[i]]);
return;
}
}
// If we reach number, then there
// are no such 3 numbers
document.write("No such triplet found <br>");
return;
}
let arr=[12, 11, 10, 5, 6, 2, 30 ]
find3Numbers(arr);
// This code is contributed by avanitrachhadiya2155
</script>
Análisis de Complejidad
- Complejidad temporal: O(n). Como la array se recorre una sola vez y no hay bucles anidados, la complejidad temporal será del orden de n.
- Espacio Auxiliar: O(n). Dado que se necesitan dos arrays adicionales para almacenar el índice del elemento menor anterior y el siguiente elemento mayor, el espacio requerido también será del orden de n
Referencia: Cómo encontrar 3 números en orden creciente e índices crecientes en una array en tiempo lineal
MÉTODO 2:
Solución: Primero encuentre dos elementos arr[i] & arr[j] tales que arr[i] < arr[j]. Luego encuentre un tercer elemento arr[k] mayor que arr[j].
Enfoque: Podemos pensar en el problema en tres términos simples.
- Primero solo necesitamos encontrar dos elementos arr[i] < arr[j] e i < j. Esto se puede hacer en tiempo lineal con solo 1 ciclo sobre el rango de la array. Por ejemplo, mientras realiza un seguimiento del elemento min, es fácil encontrar cualquier elemento posterior que sea mayor que él. Así tenemos nuestro arr[i] & arr[j].
- En segundo lugar, considera esta secuencia: {3, 4, -1, 0, 2}. Inicialmente, min es 3, arr[i] es 3 y arr[j] es 4. Mientras iteramos sobre la array, podemos realizar fácilmente un seguimiento de min y eventualmente actualizarlo a -1. Y también podemos actualizar arr[i] y arr[j] a valores más bajos, es decir, -1 y 0 respectivamente.
- En tercer lugar, tan pronto como tengamos los valores de arr[i] y arr[j], podemos comenzar a monitorear de inmediato los elementos subsiguientes en el mismo ciclo en busca de un arr[k] > arr[j]. Por lo tanto, podemos encontrar los tres valores arr[i] < arr[j] < arr[k] en un solo paso sobre la array.
Algoritmo: Iterar sobre la longitud de la array. Mantenga un registro de los minutos. Tan pronto como la siguiente iteración tenga un elemento mayor que min, hemos encontrado nuestro arr[j] y el min se guardará como arr[i]. Continúe iterando hasta que encontremos un elemento arr[k] que sea mayor que arr[j]. En caso de que los siguientes elementos tengan un valor más bajo, entonces actualizamos min, arr[i] y arr[j] a estos valores más bajos, para tener la mejor oportunidad de encontrar arr[k].
C++
// C++ Program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the triplet
void find3Numbers(vector<int>& nums)
{
// If number of elements < 3
// then no triplets are possible
if (nums.size() < 3){
cout << "No such triplet found";
return;
}
// track best sequence length
// (not current sequence length)
int seq = 1;
// min number in array
int min_num = nums[0];
// least max number in best sequence
// i.e. track arr[j] (e.g. in
// array {1, 5, 3} our best sequence
// would be {1, 3} with arr[j] = 3)
int max_seq = INT_MAX;
// save arr[i]
int store_min = min_num;
// Iterate from 1 to nums.size()
for (int i = 1; i < nums.size(); i++)
{
if (nums[i] == min_num)
continue;
else if (nums[i] < min_num)
{
min_num = nums[i];
continue;
}
// this condition is only hit
// when current sequence size is 2
else if (nums[i] < max_seq) {
// update best sequence max number
// to a smaller value
// (i.e. we've found a
// smaller value for arr[j])
max_seq = nums[i];
// store best sequence start value
// i.e. arr[i]
store_min = min_num;
}
// Increase best sequence length &
// save next number in our triplet
else if (nums[i] > max_seq)
{
// We've found our arr[k]!
// Print the output
cout << "Triplet: " << store_min <<
", " << max_seq << ", " <<
nums[i] << endl;
return;
}
}
// No triplet found
cout << "No such triplet found";
}
// Driver Code
int main() {
vector<int> nums {1,2,-1,7,5};
// Function Call
find3Numbers(nums);
}
Java
// Java Program for above approach
class Main
{
// Function to find the triplet
public static void find3Numbers(int[] nums)
{
// If number of elements < 3
// then no triplets are possible
if (nums.length < 3){
System.out.print("No such triplet found");
return;
}
// track best sequence length
// (not current sequence length)
int seq = 1;
// min number in array
int min_num = nums[0];
// least max number in best sequence
// i.e. track arr[j] (e.g. in
// array {1, 5, 3} our best sequence
// would be {1, 3} with arr[j] = 3)
int max_seq = Integer.MIN_VALUE;
// save arr[i]
int store_min = min_num;
// Iterate from 1 to nums.size()
for (int i = 1; i < nums.length; i++)
{
if (nums[i] == min_num)
continue;
else if (nums[i] < min_num)
{
min_num = nums[i];
continue;
}
// this condition is only hit
// when current sequence size is 2
else if (nums[i] < max_seq) {
// update best sequence max number
// to a smaller value
// (i.e. we've found a
// smaller value for arr[j])
max_seq = nums[i];
// store best sequence start value
// i.e. arr[i]
store_min = min_num;
}
// Increase best sequence length &
// save next number in our triplet
else if (nums[i] > max_seq)
{
seq++;
// We've found our arr[k]!
// Print the output
if (seq == 3)
{
System.out.println("Triplet: " + store_min +
", " + max_seq + ", " + nums[i]);
return;
}
max_seq = nums[i];
}
}
// No triplet found
System.out.print("No such triplet found");
}
// Driver program
public static void main(String[] args)
{
int[] nums = {1,2,-1,7,5};
// Function Call
find3Numbers(nums);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 Program for above approach
import sys
# Function to find the triplet
def find3Numbers(nums):
# If number of elements < 3
# then no triplets are possible
if (len(nums) < 3):
print("No such triplet found", end = '')
return
# Track best sequence length
# (not current sequence length)
seq = 1
# min number in array
min_num = nums[0]
# Least max number in best sequence
# i.e. track arr[j] (e.g. in
# array {1, 5, 3} our best sequence
# would be {1, 3} with arr[j] = 3)
max_seq = -sys.maxsize - 1
# Save arr[i]
store_min = min_num
# Iterate from 1 to nums.size()
for i in range(1, len(nums)):
if (nums[i] == min_num):
continue
elif (nums[i] < min_num):
min_num = nums[i]
continue
# This condition is only hit
# when current sequence size is 2
elif (nums[i] < max_seq):
# Update best sequence max number
# to a smaller value
# (i.e. we've found a
# smaller value for arr[j])
max_seq = nums[i]
# Store best sequence start value
# i.e. arr[i]
store_min = min_num
# Increase best sequence length &
# save next number in our triplet
elif (nums[i] > max_seq):
if seq == 1:
store_min = min_num
seq += 1
# We've found our arr[k]!
# Print the output
if (seq == 3):
print("Triplet: " + str(store_min) +
", " + str(max_seq) + ", " +
str(nums[i]))
return
max_seq = nums[i]
# No triplet found
print("No such triplet found", end = '')
# Driver Code
if __name__=='__main__':
nums = [ 1, 2, -1, 7, 5 ]
# Function Call
find3Numbers(nums)
# This code is contributed by rutvik_56
C#
// C# Program for above approach
using System;
class GFG {
// Function to find the triplet
static void find3Numbers(int[] nums)
{
// If number of elements < 3
// then no triplets are possible
if (nums.Length < 3){
Console.Write("No such triplet found");
return;
}
// track best sequence length
// (not current sequence length)
int seq = 1;
// min number in array
int min_num = nums[0];
// least max number in best sequence
// i.e. track arr[j] (e.g. in
// array {1, 5, 3} our best sequence
// would be {1, 3} with arr[j] = 3)
int max_seq = Int32.MinValue;
// save arr[i]
int store_min = min_num;
// Iterate from 1 to nums.size()
for (int i = 1; i < nums.Length; i++)
{
if (nums[i] == min_num)
continue;
else if (nums[i] < min_num)
{
min_num = nums[i];
continue;
}
// this condition is only hit
// when current sequence size is 2
else if (nums[i] < max_seq) {
// update best sequence max number
// to a smaller value
// (i.e. we've found a
// smaller value for arr[j])
max_seq = nums[i];
// store best sequence start value
// i.e. arr[i]
store_min = min_num;
}
// Increase best sequence length &
// save next number in our triplet
else if (nums[i] > max_seq)
{
seq++;
// We've found our arr[k]!
// Print the output
if (seq == 3)
{
Console.WriteLine("Triplet: " + store_min +
", " + max_seq + ", " + nums[i]);
return;
}
max_seq = nums[i];
}
}
// No triplet found
Console.Write("No such triplet found");
}
static void Main() {
int[] nums = {1,2,-1,7,5};
// Function Call
find3Numbers(nums);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for above approach
// Function to find the triplet
function find3Numbers(nums)
{
// If number of elements < 3
// then no triplets are possible
if (nums.length < 3)
{
document.write("No such triplet found");
return;
}
// Track best sequence length
// (not current sequence length)
let seq = 1;
// min number in array
let min_num = nums[0];
// Least max number in best sequence
// i.e. track arr[j] (e.g. in
// array {1, 5, 3} our best sequence
// would be {1, 3} with arr[j] = 3)
let max_seq = Number.MIN_VALUE;
// Save arr[i]
let store_min = min_num;
// Iterate from 1 to nums.size()
for(let i = 1; i < nums.length; i++)
{
if (nums[i] == min_num)
continue;
else if (nums[i] < min_num)
{
min_num = nums[i];
continue;
}
// This condition is only hit
// when current sequence size is 2
else if (nums[i] < max_seq)
{
// Update best sequence max number
// to a smaller value
// (i.e. we've found a
// smaller value for arr[j])
max_seq = nums[i];
// Store best sequence start value
// i.e. arr[i]
store_min = min_num;
}
// Increase best sequence length &
// save next number in our triplet
else if (nums[i] > max_seq)
{
seq++;
// We've found our arr[k]!
// Print the output
if (seq == 3)
{
document.write("Triplet: " + store_min +
", " + max_seq + ", " +
nums[i]);
return;
}
max_seq = nums[i];
}
}
// No triplet found
document.write("No such triplet found");
}
// Driver code
let nums = [1, 2, -1, 7, 5];
// Function Call
find3Numbers(nums);
// This code is contributed by suresh07
</script>
Producción
Triplet: 1, 2, 7
Análisis de Complejidad:
Complejidad temporal: O(n). Como la array se recorre una sola vez y no hay bucles anidados, la complejidad temporal será del orden de n.
Espacio Auxiliar: O(1).
Ejercicio:
- Encuentre una subsecuencia de tamaño 3 tal que arr[i] < arr[j] > arr[k].
- Encuentre una subsecuencia ordenada de tamaño 4 en tiempo lineal
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA