Dada una array (arr[]) de N enteros, encuentre una subsecuencia de 4 elementos tal que a[i] < a[j] < a[k] < a[l] e i < j < k < l en O( n ) tiempo. Si hay varios Quadruplet de este tipo , simplemente imprima cualquiera de ellos.
Ejemplos:
Entrada: arr[] = {7, 4, 6, 10, 11, 13, 1, 2}
Salida: 4 6 10 13
Explicación: Como 4 < 6 < 10 <13, donde i < j < k < l, arr [i] <arr[j] <arr[k] <arr[l]Entrada: arr[] = {1, 7, 4, 5, 3, 6}
Salida: 1 4 5 6
Explicación: As 1 < 4 < 5 < 6, donde i < j < k < l, arr[i] < arr[j] < arr[k] < arr[l]Entrada: arr[] = {4, 3, 1, 7}
Salida: No existe tal Cuatrillizo.
Enfoque ingenuo:
Sugerencia: utilice el espacio auxiliar.
El enfoque es encontrar un elemento que tenga dos elementos más pequeños 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 Cuatrillizo que satisface los criterios. , de lo contrario no hay tal Quadrupletis presente.
Algoritmo:
- Cree una array auxiliar más pequeña[n] , que almacena el índice de un número que es el valor 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 second_smaller[n] , que almacena el índice de un número que es el segundo valor 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[n] , que almacena el índice de un número que tiene un valor mayor que arr[i] y está en el lado derecho. La array contiene -1 si no existe tal elemento.
- Finalmente, recorra tres arrays y encuentre el índice en el que mayor[i] != -1 , segundo_menor[i] != -1 y menor[segundo_menor[i]] != -1 y si la condición coincide, el Cuatrillizo será arr[menor [segundo_menor[i]]] , arr[segundo_menor[i]] , arr[i] y arr[mayor[i]] .
A continuación se muestra la implementación del enfoque anterior: –
C++
// C++ program to find a sorted
// sub-sequence of size 4
#include <bits/stdc++.h>
using namespace std;
void findQuadruplet(int arr[], int n)
{
// If number of elements < 4
// then no Quadruple are possible
if (n < 4) {
cout << "No such Quadruple found";
return;
}
bool flag = false;
// to check true or false
// Index of greatest element
// from right side
int max = n - 1;
// Index of smallest element
// from left side
int min = 0;
// Index of second smallest element
// from left side
int second_min = -1;
// Create another array that will
// store index of a minimum element
// on left side. If there is no minimum
// element on left side,
// then smaller[i] = -1
int* smaller = new int[n];
// Create another array that will
// store index of a second minimum
// element on left side. If there is no
// second minimum element on left side,
// then second_smaller[i] = -1
int* second_smaller = new int[n];
// First entry of both smaller and
// second_smaller is -1.
smaller[0] = -1;
second_smaller[0] = -1;
for (int i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[0] = -1;
second_smaller[0] = -1;
}
else {
smaller[i] = min;
if (second_min != -1) {
if (arr[second_min] < arr[i]) {
second_smaller[i] = second_min;
}
}
else {
second_smaller[i] = -1;
}
if (arr[i] < arr[second_min]
|| second_min == -1) {
second_min = i;
}
}
}
// 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] = -1
int* greater = new int[n];
// Last entry of greater is -1.
greater[n - 1] = -1;
for (int i = n - 2; i >= 0; i--) {
if (arr[max] <= arr[i]) {
max = i;
greater[i] = -1;
}
else {
greater[i] = max;
}
}
// Now we need to find a number which
// has a greater on its right side and
// two small on it's left side.
for (int i = 0; i < n; i++) {
if (smaller[second_smaller[i]] != -1
&& second_smaller[i] != -1
&& greater[i] != -1) {
cout << "Quadruplets: "
<< arr[smaller[second_smaller[i]]] << " "
<< arr[second_smaller[i]] << " " << arr[i]
<< " " << arr[greater[i]] << "\n";
flag = true;
break;
}
}
if (flag == false)
cout << "No such Quadruplet found";
// Free the dynamically allocated memory
// to avoid memory leak
delete[] smaller;
delete[] greater;
delete[] second_smaller;
return;
}
// Driver Code
int main()
{
int arr[] = { 1, 7, 4, 5, 3, 6 };
int N = sizeof(arr) / sizeof(int);
findQuadruplet(arr, N);
return 0;
}
Java
// Java program to find a sorted
// sub-sequence of size 4
class GFG {
static void findQuadruplet(int arr[], int n)
{
// If number of elements < 4
// then no Quadruple are possible
if (n < 4) {
System.out.println("No such Quadruple found");
return;
}
boolean flag = false;
// to check true or false
// Index of greatest element
// from right side
int max = n - 1;
// Index of smallest element
// from left side
int min = 0;
// Index of second smallest element
// from left side
int second_min = -1;
// Create another array that will
// store index of a minimum element
// on left side. If there is no minimum
// element on left side,
// then smaller[i] = -1
int[] smaller = new int[n];
// Create another array that will
// store index of a second minimum
// element on left side. If there is no
// second minimum element on left side,
// then second_smaller[i] = -1
int[] second_smaller = new int[n];
// First entry of both smaller and
// second_smaller is -1.
smaller[0] = -1;
second_smaller[0] = -1;
for (int i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[0] = -1;
second_smaller[0] = -1;
}
else {
smaller[i] = min;
if (second_min != -1) {
if (arr[second_min] < arr[i]) {
second_smaller[i] = second_min;
}
}
else {
second_smaller[i] = -1;
}
if (second_min == -1
|| arr[i] < arr[second_min]) {
second_min = i;
}
}
}
// 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] = -1
int[] greater = new int[n];
// Last entry of greater is -1.
greater[n - 1] = -1;
for (int i = n - 2; i >= 0; i--) {
if (arr[max] <= arr[i]) {
max = i;
greater[i] = -1;
}
else {
greater[i] = max;
}
}
// Now we need to find a number which
// has a greater on its right side and
// two small on it's left side.
for (int i = 0; i < n; i++) {
if (second_smaller[i] != -1
&& smaller[second_smaller[i]] != -1
&& greater[i] != -1) {
System.out.println(
"Quadruplets: "
+ arr[smaller[second_smaller[i]]] + " "
+ arr[second_smaller[i]] + " " + arr[i]
+ " " + arr[greater[i]]);
flag = true;
break;
}
}
if (flag == false)
System.out.println("No such Quadruplet found");
return;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 7, 4, 5, 3, 6 };
int N = arr.length;
findQuadruplet(arr, N);
}
}
// This code is contributed by Lovely Jain
Python3
# Python3 program for the above approach
# program to find a sorted
# sub-sequence of size 4
def findQuadruplet(arr, n) :
# If number of elements < 4
# then no Quadruple are possible
if (n < 4) :
print("No such Quadruple found")
return
flag = False
# to check true or false
# Index of greatest element
# from right side
max = n - 1
# Index of smallest element
# from left side
min = 0
# Index of second smallest element
# from left side
second_min = -1
# Create another array that will
# store index of a minimum element
# on left side. If there is no minimum
# element on left side,
# then smaller[i] = -1
smaller = [0] * n
# Create another array that will
# store index of a second minimum
# element on left side. If there is no
# second minimum element on left side,
# then second_smaller[i] = -1
second_smaller = [0] * n
# First entry of both smaller and
# second_smaller is -1.
smaller[0] = -1
second_smaller[0] = -1
for i in range(1, n) :
if (arr[i] <= arr[min]) :
min = i
smaller[0] = -1
second_smaller[0] = -1
else :
smaller[i] = min
if (second_min != -1) :
if (arr[second_min] < arr[i]) :
second_smaller[i] = second_min
else :
second_smaller[i] = -1
if (arr[i] < arr[second_min]
or second_min == -1) :
second_min = i
# 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] = -1
greater = [0] * n
# Last entry of greater is -1.
greater[n - 1] = -1
for i in range(n-2, -1, -1) :
if (arr[max] <= arr[i]) :
max = i
greater[i] = -1
else :
greater[i] = max
# Now we need to find a number which
# has a greater on its right side and
# two small on it's left side.
for i in range(n) :
if (smaller[second_smaller[i]] != -1
and second_smaller[i] != -1
and greater[i] != -1) :
print("Quadruplets:", arr[smaller[second_smaller[i]]], end = " ")
print(arr[second_smaller[i]], end = " ")
print(arr[i], end = " ")
print(arr[greater[i]])
flag = True
break
if (flag == False) :
print( "No such Quadruplet found")
return
# Driver Code
arr = [ 1, 7, 4, 5, 3, 6 ]
N = len(arr)
findQuadruplet(arr, N)
# This code is contributed by sanjoy_62.
C#
// C# program to find a sorted
// sub-sequence of size 4
using System;
public class GFG {
static void findQuadruplet(int []arr, int n)
{
// If number of elements < 4
// then no Quadruple are possible
if (n < 4) {
Console.WriteLine("No such Quadruple found");
return;
}
bool flag = false;
// to check true or false
// Index of greatest element
// from right side
int max = n - 1;
// Index of smallest element
// from left side
int min = 0;
// Index of second smallest element
// from left side
int second_min = -1;
// Create another array that will
// store index of a minimum element
// on left side. If there is no minimum
// element on left side,
// then smaller[i] = -1
int[] smaller = new int[n];
// Create another array that will
// store index of a second minimum
// element on left side. If there is no
// second minimum element on left side,
// then second_smaller[i] = -1
int[] second_smaller = new int[n];
// First entry of both smaller and
// second_smaller is -1.
smaller[0] = -1;
second_smaller[0] = -1;
for (int i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[0] = -1;
second_smaller[0] = -1;
}
else {
smaller[i] = min;
if (second_min != -1) {
if (arr[second_min] < arr[i]) {
second_smaller[i] = second_min;
}
}
else {
second_smaller[i] = -1;
}
if (second_min == -1
|| arr[i] < arr[second_min]) {
second_min = i;
}
}
}
// 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] = -1
int[] greater = new int[n];
// Last entry of greater is -1.
greater[n - 1] = -1;
for (int i = n - 2; i >= 0; i--) {
if (arr[max] <= arr[i]) {
max = i;
greater[i] = -1;
}
else {
greater[i] = max;
}
}
// Now we need to find a number which
// has a greater on its right side and
// two small on it's left side.
for (int i = 0; i < n; i++) {
if (second_smaller[i] != -1
&& smaller[second_smaller[i]] != -1
&& greater[i] != -1) {
Console.WriteLine(
"Quadruplets: "
+ arr[smaller[second_smaller[i]]] + " "
+ arr[second_smaller[i]] + " " + arr[i]
+ " " + arr[greater[i]]);
flag = true;
break;
}
}
if (flag == false)
Console.WriteLine("No such Quadruplet found");
return;
}
// Driver Code
public static void Main(string []args)
{
int []arr = { 1, 7, 4, 5, 3, 6 };
int N = arr.Length;
findQuadruplet(arr, N);
}
}
// This code is contributed by AnkThon
Javascript
// JavaScript program to find a sorted
// sub-sequence of size 4
function findQuadruplet(arr, n)
{
// If number of elements < 4
// then no Quadruple are possible
if (n < 4) {
console.log("No such Quadruple found");
return;
}
let flag = false;
// to check true or false
// Index of greatest element
// from right side
let max = n - 1;
// Index of smallest element
// from left side
let min = 0;
// Index of second smallest element
// from left side
let second_min = -1;
// Create another array that will
// store index of a minimum element
// on left side. If there is no minimum
// element on left side,
// then smaller[i] = -1
let smaller = new Array(n).fill(0);
// Create another array that will
// store index of a second minimum
// element on left side. If there is no
// second minimum element on left side,
// then second_smaller[i] = -1
let second_smaller = new Array(n).fill(0);
// First entry of both smaller and
// second_smaller is -1.
smaller[0] = -1;
second_smaller[0] = -1;
for (let i = 1; i < n; i++) {
if (arr[i] <= arr[min]) {
min = i;
smaller[0] = -1;
second_smaller[0] = -1;
}
else {
smaller[i] = min;
if (second_min != -1) {
if (arr[second_min] < arr[i]) {
second_smaller[i] = second_min;
}
}
else {
second_smaller[i] = -1;
}
if (arr[i] < arr[second_min]
|| second_min == -1) {
second_min = i;
}
}
}
// 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] = -1
let greater = new Array(n).fill(0);
// Last entry of greater is -1.
greater[n - 1] = -1;
for (let i = n - 2; i >= 0; i--) {
if (arr[max] <= arr[i]) {
max = i;
greater[i] = -1;
}
else {
greater[i] = max;
}
}
// Now we need to find a number which
// has a greater on its right side and
// two small on it's left side.
for (let i = 0; i < n; i++) {
if ((smaller[second_smaller[i]] != -1)
&& (second_smaller[i] != -1)
&& (greater[i] != -1)) {
console.log("Quadruplets: ", arr[smaller[second_smaller[i]]] , arr[second_smaller[i]], arr[i], arr[greater[i]]);
flag = true;
break;
}
}
if (flag == false)
console.log("No such Quadruplet found");
return;
}
// Driver Code
let arr = [ 1, 7, 4, 5, 3, 6 ];
let N = arr.length;
findQuadruplet(arr, N);
// This code is contributed by phasing17
Producción
Quadruplets: 1 4 5 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente: siga la siguiente idea para resolver el problema:
La idea es encontrar primero tres elementos arr[i] , arr[j] , arr[k] tales que arr[i] < arr[j] < arr[k] . Luego encuentre un cuarto elemento arr[l] mayor que arr[k] recorriendo el arreglo con O(n) tiempo y O(1) espacio. Entonces podemos imprimir el Cuatrillizo como arr[i] , arr[j] , arr[k] , arr[l] .
Siga los pasos para resolver el problema:
- Iterar sobre la longitud de la array.
- Mantenga un registro del elemento min.
- Tan pronto como la próxima iteración tenga un elemento mayor que min, hemos encontrado nuestro segundo min y el min se guardará como arr[i] .
- Continúe iterando hasta que se encuentre un elemento mayor que arr[j] y obtenga nuestro arr[k] y el segundo min se guardará como arr[j] y min como arr[i]
- Luego, mientras continúa la iteración, intente encontrar un número mayor que arr[k] , que es arr[l] .
- Entonces la secuencia de Cuatrillizo será min, segundo min, arr[k] y arr[l] (donde min < segundo min < arr[k] < arr[l].
A continuación se muestra la implementación del enfoque anterior: –
C++
// C++ program to find a sorted
// sub-sequence of size 4
#include <bits/stdc++.h>
using namespace std;
void findQuadruplet(int arr[], int n)
{
// If number of elements < 4
// then no Quadruple are possible
if (n < 4) {
cout << "No such Quadruple found";
return;
}
// Initializing the variables with
// INT_MAX macros.
// To store the min element.
int small = INT_MAX;
// To store the second minimum element.
int second_small = INT_MAX;
// To store the middle element.
int mid = INT_MAX;
// To remember the mid and the
// minimum element.
int min = 0;
int main_mid = 0;
int main_min = 0;
// Traversing the array to find
// the Quadruple
for (int i = 0; i < n; i++) {
if (arr[i] <= small) {
small = arr[i];
}
else if (arr[i] <= second_small) {
second_small = arr[i];
min = small;
}
else if (arr[i] <= mid) {
mid = arr[i];
main_mid = second_small;
main_min = min;
}
else {
// If the number is greater than mid.
cout << "Quadruplets: " << main_min
<< " " << main_mid << " "
<< mid << " " << arr[i];
// Return if Quadruple is found.
return;
}
}
// If no Quadruple is found
cout << "No such Quadruple";
return;
}
// Driver program
int main()
{
int arr[] = { 1, 7, 4, 5, 3, 6 };
int N = sizeof(arr) / sizeof(int);
findQuadruplet(arr, N);
return 0;
}
Java
// Java program to find a sorted
// sub-sequence of size 4
public class GFG {
static void findQuadruplet(int arr[], int n)
{
int INT_MAX = Integer.MAX_VALUE;
// If number of elements < 4
// then no Quadruple are possible
if (n < 4) {
System.out.print("No such Quadruple found");
return;
}
// Initializing the variables with
// INT_MAX macros.
// To store the min element.
int small = INT_MAX;
// To store the second minimum element.
int second_small = INT_MAX;
// To store the middle element.
int mid = INT_MAX;
// To remember the mid and the
// minimum element.
int min = 0;
int main_mid = 0;
int main_min = 0;
// Traversing the array to find
// the Quadruple
for (int i = 0; i < n; i++) {
if (arr[i] <= small) {
small = arr[i];
}
else if (arr[i] <= second_small) {
second_small = arr[i];
min = small;
}
else if (arr[i] <= mid) {
mid = arr[i];
main_mid = second_small;
main_min = min;
}
else {
// If the number is greater than mid.
System.out.print("Quadruplets: " + main_min + " " + main_mid + " " + mid + " " + arr[i]);
// Return if Quadruple is found.
return;
}
}
// If no Quadruple is found
System.out.print("No such Quadruple");
return;
}
// Driver program
public static void main (String[] args)
{
int arr[] = { 1, 7, 4, 5, 3, 6 };
int N = arr.length;
findQuadruplet(arr, N);
}
}
// This code is contributed by AnkThon
Python3
# Python program to find a sorted
# sub-sequence of size 4
import sys
def findQuadruplet(arr, n):
# If number of elements < 4
# then no Quadruple are possible
if (n < 4):
print("No such Quadruple found")
return
# Initializing the variables with
# INT_MAX macros.
# To store the min element.
small = sys.maxsize
# To store the second minimum element.
second_small = sys.maxsize
# To store the middle element.
mid = sys.maxsize
# To remember the mid and the
# minimum element.
min = 0
main_mid = 0
main_min = 0
# Traversing the array to find
# the Quadruple
for i in range(n):
if (arr[i] <= small):
small = arr[i]
elif (arr[i] <= second_small):
second_small = arr[i]
min = small
elif (arr[i] <= mid):
mid = arr[i]
main_mid = second_small
main_min = min
else:
# If the number is greater than mid.
print(f"Quadruplets: {main_min} {main_mid} {mid} {arr[i]}")
# Return if Quadruple is found.
return
# If no Quadruple is found
print("No such Quadruple")
return
# Driver program
arr = [ 1, 7, 4, 5, 3, 6 ]
N = len(arr)
findQuadruplet(arr, N);
# This code is contributed by shinjanpatra
C#
// C# program to find a sorted
// sub-sequence of size 4
using System;
public class GFG
{
static void findQuadruplet(int[] arr, int n)
{
int INT_MAX = int.MaxValue;
// If number of elements < 4
// then no Quadruple are possible
if (n < 4)
{
Console.Write("No such Quadruple found");
return;
}
// Initializing the variables with
// INT_MAX macros.
// To store the min element.
int small = INT_MAX;
// To store the second minimum element.
int second_small = INT_MAX;
// To store the middle element.
int mid = INT_MAX;
// To remember the mid and the
// minimum element.
int min = 0;
int main_mid = 0;
int main_min = 0;
// Traversing the array to find
// the Quadruple
for (int i = 0; i < n; i++)
{
if (arr[i] <= small)
{
small = arr[i];
}
else if (arr[i] <= second_small)
{
second_small = arr[i];
min = small;
}
else if (arr[i] <= mid)
{
mid = arr[i];
main_mid = second_small;
main_min = min;
}
else
{
// If the number is greater than mid.
Console.Write("Quadruplets: " + main_min + " " + main_mid + " " + mid + " " + arr[i]);
// Return if Quadruple is found.
return;
}
}
// If no Quadruple is found
Console.Write("No such Quadruple");
return;
}
// Driver program
public static void Main()
{
int[] arr = { 1, 7, 4, 5, 3, 6 };
int N = arr.Length;
findQuadruplet(arr, N);
}
}
// This code is contributed by gfgking
Javascript
<script>
// JavaScript code for the above approach
function findQuadruplet(arr, n) {
// If number of elements < 4
// then no Quadruple are possible
if (n < 4) {
document.write("No such Quadruple found");
return;
}
// Initializing the variables with
// Number.MAX_VALUE macros.
// To store the min element.
let small = Number.MAX_VALUE;
// To store the second minimum element.
let second_small = Number.MAX_VALUE;
// To store the middle element.
let mid = Number.MAX_VALUE;
// To remember the mid and the
// minimum element.
let min = 0;
let main_mid = 0;
let main_min = 0;
// Traversing the array to find
// the Quadruple
for (let i = 0; i < n; i++) {
if (arr[i] <= small) {
small = arr[i];
}
else if (arr[i] <= second_small) {
second_small = arr[i];
min = small;
}
else if (arr[i] <= mid) {
mid = arr[i];
main_mid = second_small;
main_min = min;
}
else {
// If the number is greater than mid.
document.write("Quadruplets: " + main_min
+ " " + main_mid + " "
+ mid + " " + arr[i]);
// Return if Quadruple is found.
return;
}
}
// If no Quadruple is found
document.write("No such Quadruple");
return;
}
// Driver program
let arr = [1, 7, 4, 5, 3, 6];
let N = arr.length;
findQuadruplet(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción
Quadruplets: 1 4 5 6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shoumikmanna y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA