Dada una array , arr[] de tamaño N , la tarea es reorganizar los elementos de la array para maximizar el recuento de tripletes ( i, j, k ) que satisfacen la condición arr[i] > arr[j] < arr[k] y yo < j < k .
Ejemplos:
Entrada: arr[] = {1, 4, 3, 3, 2, 2, 5}
Salida:
Recuento de trillizos: 3
Array: {3, 1, 3, 2, 4, 2, 5}
Explicación:
Reorganizar la array a {3, 1, 3, 2, 4, 2, 5} que da el número máximo de tripletes {(3, 1, 3), (3, 2, 4), (4, 2, 5)} que satisface la condición dada.
Por lo tanto, el conteo requerido de trillizos es 3.Entrada: array[] = {1, 2, 3, 4, 5, 6, 7, 7}
Salida:
Recuento de trillizos = 3
Array = {5, 1, 6, 2, 7, 3, 7, 4}
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las permutaciones posibles de la array y contar el número de tripletes que satisfacen la condición dada. Finalmente, imprima el conteo de tripletes y las permutaciones de la array dada que contienen el conteo máximo de tripletes con la condición dada.
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es ordenar primero la array dada y colocar la primera mitad de la array dada en índices impares y la última mitad de la array en índices pares en una array temporal. Finalmente, imprima la array temporal y el conteo de trillizos con la condición dada. Siga los pasos a continuación para resolver el problema:
- Inicialice una array temporal, digamos temp[] , para almacenar las permutaciones de la array dada.
- Ordena la array dada , arr[] .
- Coloque la primera mitad de la array dada en índices impares de la array temporal .
- Coloque la última mitad de la array dada en los índices pares de la array temporal .
- Finalmente, imprima el conteo de tripletes con las condiciones dadas en temp[] y temp array.
A continuación se muestran las implementaciones del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange the array
// to maximize the count of triplets
void ctTriplets(int arr[], int N)
{
// Sort the given array
sort(arr, arr + N);
// Stores the permutations
// of the given array
vector<int> temp(N);
// Stores the index
// of the given array
int index = 0;
// Place the first half
// of the given array
for (int i = 1; i < N;
i += 2) {
temp[i]
= arr[index++];
}
// Place the last half
// of the given array
for (int i = 0; i < N;
i += 2) {
temp[i]
= arr[index++];
}
// Stores the count
// of triplets
int ct = 0;
for (int i = 0; i < N; i++) {
// Check the given conditions
if (i > 0 && i + 1 < N) {
if (temp[i] < temp[i + 1]
&& temp[i] < temp[i - 1]) {
ct++;
}
}
}
cout << "Count of triplets:"
<< ct << endl;
cout << "Array:";
for (int i = 0; i < N;
i++) {
cout << temp[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
ctTriplets(arr, N);
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.Arrays;
class GFG{
// Function to rearrange the array
// to maximize the count of triplets
static void ctTriplets(int arr[], int N)
{
// Sort the given array
Arrays.sort(arr);
// Stores the permutations
// of the given array
int[] temp = new int[N];
// Stores the index
// of the given array
int index = 0;
// Place the first half
// of the given array
for(int i = 1; i < N; i += 2)
{
temp[i] = arr[index++];
}
// Place the last half
// of the given array
for(int i = 0; i < N; i += 2)
{
temp[i] = arr[index++];
}
// Stores the count
// of triplets
int ct = 0;
for(int i = 0; i < N; i++)
{
// Check the given conditions
if (i > 0 && i + 1 < N)
{
if (temp[i] < temp[i + 1] &&
temp[i] < temp[i - 1])
{
ct++;
}
}
}
System.out.println("Count of triplets:" + ct );
System.out.print("Array:");
for(int i = 0; i < N; i++)
{
System.out.print(temp[i] + " ");
}
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int N = arr.length;
ctTriplets(arr, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to implement
# the above approach
# Function to rearrange the array
# to maximize the count of triplets
def ctTriplets(arr, N):
# Sort the given array
arr.sort()
# Stores the permutations
# of the given array
temp = [0] * N
# Stores the index
# of the given array
index = 0
# Place the first half
# of the given array
for i in range(1, N, 2):
temp[i] = arr[index]
index += 1
# Place the last half
# of the given array
for i in range(0, N, 2):
temp[i] = arr[index]
index += 1
# Stores the count
# of triplets
ct = 0
for i in range(N):
# Check the given conditions
if (i > 0 and i + 1 < N):
if (temp[i] < temp[i + 1] and
temp[i] < temp[i - 1]):
ct += 1
print("Count of triplets:", ct)
print("Array:", end = "")
for i in range(N):
print(temp[i], end = " ")
# Driver Code
arr = [ 1, 2, 3, 4, 5, 6 ]
N = len(arr)
ctTriplets(arr, N)
# This code is contributed by sanjoy_62
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to rearrange the array
// to maximize the count of triplets
static void ctTriplets(int[] arr, int N)
{
// Sort the given array
Array.Sort(arr);
// Stores the permutations
// of the given array
int[] temp = new int[N];
// Stores the index
// of the given array
int index = 0;
// Place the first half
// of the given array
for(int i = 1; i < N; i += 2)
{
temp[i] = arr[index++];
}
// Place the last half
// of the given array
for(int i = 0; i < N; i += 2)
{
temp[i] = arr[index++];
}
// Stores the count
// of triplets
int ct = 0;
for(int i = 0; i < N; i++)
{
// Check the given conditions
if (i > 0 && i + 1 < N)
{
if (temp[i] < temp[i + 1] &&
temp[i] < temp[i - 1])
{
ct++;
}
}
}
Console.WriteLine("Count of triplets:" + ct );
Console.Write("Array:");
for(int i = 0; i < N; i++)
{
Console.Write(temp[i] + " ");
}
}
// Driver Code
public static void Main ()
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
int N = arr.Length;
ctTriplets(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to rearrange the array
// to maximize the count of triplets
function ctTriplets(arr, N)
{
// Sort the given array
arr.sort();
// Stores the permutations
// of the given array
let temp = [];
// Stores the index
// of the given array
let index = 0;
// Place the first half
// of the given array
for(let i = 1; i < N; i += 2)
{
temp[i] = arr[index++];
}
// Place the last half
// of the given array
for(let i = 0; i < N; i += 2)
{
temp[i] = arr[index++];
}
// Stores the count
// of triplets
let ct = 0;
for(let i = 0; i < N; i++)
{
// Check the given conditions
if (i > 0 && i + 1 < N)
{
if (temp[i] < temp[i + 1] &&
temp[i] < temp[i - 1])
{
ct++;
}
}
}
document.write("Count of triplets:" + ct + "<br/>");
document.write("Array:");
for(let i = 0; i < N; i++)
{
document.write(temp[i] + " ");
}
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5, 6 ];
let N = arr.length;
ctTriplets(arr, N);
// This code is contributed by target_2.
</script>
Count of triplets:2 Array:4 1 5 2 6 3
Complejidad de tiempo : O(N*log(N))
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por aaryaverma112 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA