Dada una array arr[] de tamaño N. La tarea es encontrar el número de secuencias en las que se cumple cualquiera de las siguientes condiciones:
- La secuencia dada se puede reorganizar en orden estrictamente creciente , o
- La secuencia dada se puede reorganizar en orden estrictamente decreciente , o
- La secuencia dada se puede reorganizar en orden de secuencia de Hill .
La tarea es verificar si la secuencia Hill favorable es posible y luego imprimir la secuencia posible.
Ejemplos:
Entrada: arr[] ={5, 7, 2, 1, 2}
Salida: 1 2 5 7 2
Explicación: Aquí una de esas secuencias es la siguiente
: s1 = {1, 2, 5, 7, 2}Entrada: arr[] ={2, 4, 1, 2, 5, 6, 3}
Salida: 1, 2, 3, 4, 5, 6, 2
Explicación: Aquí dos secuencias de este tipo son las siguientes
: s1 ={1 , 2, 3, 4, 5, 6, 2} o,
– s2 ={1, 2, 3, 6, 5, 4, 2}
Enfoque: La idea es usar hashing y sorting para resolver el problema. Compruebe si hay elementos cuya frecuencia es mayor que 2, entonces no es posible. Siga los pasos a continuación para resolver el problema:
- Inicialice el indicador de variable como 0 .
- Inicialice map<int, int> freq[].
- Inicialice el vector<int> a[].
- Itere sobre el rango [0, n) usando la variable i y realice las siguientes tareas:
- Inserte el valor de arr[i] en la array a[].
- Aumente el recuento de freq[arr[i]] en 1.
- Inicialice la variable max como el elemento máximo en la array a[].
- Inicialice la variable freqsum como 0 .
- Recorra el mapa freq[] usando la variable x y realice las siguientes tareas:
- Si x.segundo mayor que igual a 3 , establezca el indicador como -1.
- Recorra el mapa freq[] usando la variable x y realice las siguientes tareas:
- Cuente todos los elementos distintos en la variable freqsum .
- Si freq[max] es igual a 2 , establezca el indicador como -1 ; de lo contrario, establezca el indicador como 1.
- Si el indicador es igual a 1 , realice las siguientes tareas:
- Recorra el mapa freq[] usando la variable x y realice las siguientes tareas:
- Si x.segundo es igual a 1 , entonces empújelo en el vector descendente[]; de lo contrario, empújelo también en el ascendente[] .
- Ordene el vector descendente[] en orden ascendente y ascendente[] en orden descendente.
- Recorra el mapa freq[] usando la variable x y realice las siguientes tareas:
- Después de realizar los pasos anteriores, imprima el resultado.
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;
void find(int arr[], int n)
{
// Flag will indicate whether
// sequence is possible or not
int flag = 0;
map<int, int> freq;
vector<int> a;
for (int i = 0; i < n; i++) {
a.push_back(arr[i]);
freq[arr[i]]++;
}
// Max element in <a>
int max = *max_element(a.begin(), a.end());
// Store only unique elements count
int freqsum = 0;
// If any element having freq more than 2
for (auto& x : freq) {
// Hill sequence isn't possible
if (x.second >= 3)
flag = -1;
}
vector<int> ascending, descending;
// Counting all distinct elements only
for (auto& x : freq) {
// Having freq more than 1 should
// be count only 1'nce
if (x.second > 1)
freqsum += 1;
else
freqsum += x.second;
}
// All elements are distinct
// Hill sequence is possible
if (a.size() == freqsum)
flag = 1;
else {
// Max element appeared morethan 1nce
// Hill sequence isn't possible
if (freq[max] >= 2)
flag = -1;
// Hill sequence is possible
else
flag = 1;
}
// Print favourable sequence if flag==1
// Hill sequence is possible
if (flag == 1) {
for (auto& x : freq) {
// If an element's freq==1
if (x.second == 1)
descending.push_back(x.first);
else {
// If an element's freq==2
descending.push_back(x.first);
ascending.push_back(x.first);
}
}
sort(descending.begin(), descending.end());
sort(ascending.begin(), ascending.end(),
greater<int>());
for (auto& x : descending)
cout << x << " ";
for (auto& x : ascending)
cout << x << " ";
}
else {
cout << "Not Possible!\n";
}
}
// Driver Code
int main()
{
int n = 5;
int arr[n] = { 5, 7, 2, 1, 2 };
find(arr, n);
return 0;
}
Java
// JAVA program for the above approach
import java.util.*;
class GFG {
public static void find(int arr[], int n)
{
// Flag will indicate whether
// sequence is possible or not
int flag = 0;
HashMap<Integer, Integer> freq = new HashMap<>();
ArrayList<Integer> a = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
a.add(arr[i]);
if (freq.containsKey(arr[i])) {
freq.put(arr[i], freq.get(arr[i]) + 1);
}
else {
freq.put(arr[i], 1);
}
}
// Max element in <a>
int max = Collections.max(a);
// Store only unique elements count
int freqsum = 0;
// If any element having freq more than 2
for (Map.Entry<Integer, Integer> i :
freq.entrySet()) {
// Hill sequence isn't possible
if (i.getValue() >= 3)
flag = -1;
}
ArrayList<Integer> ascending
= new ArrayList<Integer>();
ArrayList<Integer> descending
= new ArrayList<Integer>();
// Counting all distinct elements only
for (Map.Entry<Integer, Integer> i :
freq.entrySet()) {
// Having freq more than 1 should
// be count only 1'nce
if (i.getValue() > 1)
freqsum += 1;
else
freqsum += i.getValue();
}
// All elements are distinct
// Hill sequence is possible
if (a.size() == freqsum)
flag = 1;
else {
// Max element appeared morethan 1nce
// Hill sequence isn't possible
if (freq.get(max) >= 2)
flag = -1;
// Hill sequence is possible
else
flag = 1;
}
// Print favourable sequence if flag==1
// Hill sequence is possible
if (flag == 1) {
for (Map.Entry<Integer, Integer> i :
freq.entrySet()) {
// If an element's freq==1
if (i.getValue() == 1)
descending.add(i.getKey());
else {
// If an element's freq==2
descending.add(i.getKey());
ascending.add(i.getKey());
}
}
Collections.sort(descending);
Collections.sort(ascending,
Collections.reverseOrder());
for (int i = 0; i < descending.size(); i++)
System.out.print(descending.get(i) + " ");
for (int i = 0; i < ascending.size(); i++)
System.out.print(ascending.get(i) + " ");
}
else {
System.out.println("Not Possible!");
}
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
int[] arr = new int[n];
arr[0] = 5;
arr[1] = 7;
arr[2] = 2;
arr[3] = 1;
arr[4] = 2;
find(arr, n);
}
}
// This code is contributed by Taranpreet
Python3
# Python code for the above approach
def find(arr, n):
# Flag will indicate whether
# sequence is possible or not
flag = 0
freq = {}
a = []
for i in range(n):
a.append(arr[i])
if (arr[i] in freq):
freq[arr[i]] += 1
else:
freq[arr[i]] = 1
# Max element in <a>
_max = max(a)
# Store only unique elements count
freqsum = 0
# If any element having freq more than 2
for k in freq.keys():
# Hill sequence isn't possible
if (freq[k] >= 3):
flag = -1
ascending = []
descending = []
# Counting all distinct elements only
for k in freq:
# Having freq more than 1 should
# be count only 1'nce
if (freq[k] > 1):
freqsum += 1
else:
freqsum += freq[k]
# All elements are distinct
# Hill sequence is possible
if (len(a) == freqsum):
flag = 1
else:
# Max element appeared morethan 1nce
# Hill sequence isn't possible
if (freq[_max] >= 2):
flag = -1
# Hill sequence is possible
else:
flag = 1
# Print favourable sequence if flag==1
# Hill sequence is possible
if (flag == 1):
for k in freq.keys():
# If an element's freq==1
if (freq[k] == 1):
descending.append(k)
else:
# If an element's freq==2
descending.append(k)
ascending.append(k)
descending.sort()
ascending.sort()
for x in descending:
print(x, end=" ")
for x in ascending:
print(x, end=" ")
else:
print("Not Possible!" + '<br>')
# Driver Code
n = 5
arr = [5, 7, 2, 1, 2]
find(arr, n)
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG {
public static void find(int []arr, int n)
{
// Flag will indicate whether
// sequence is possible or not
int flag = 0;
Dictionary<int, int> freq = new Dictionary<int, int>();
List<int> a = new List<int>();
for (int i = 0; i < n; i++) {
a.Add(arr[i]);
if (freq.ContainsKey(arr[i])) {
freq[arr[i]] = freq[arr[i]] + 1;
}
else {
freq.Add(arr[i], 1);
}
}
// Max element in <a>
int max = a.Max();
// Store only unique elements count
int freqsum = 0;
// If any element having freq more than 2
foreach (KeyValuePair<int, int> i in
freq) {
// Hill sequence isn't possible
if (i.Value >= 3)
flag = -1;
}
List<int> ascending
= new List<int>();
List<int> descending
= new List<int>();
// Counting all distinct elements only
foreach (KeyValuePair<int, int> i in
freq) {
// Having freq more than 1 should
// be count only 1'nce
if (i.Value > 1)
freqsum += 1;
else
freqsum += i.Value;
}
// All elements are distinct
// Hill sequence is possible
if (a.Count == freqsum)
flag = 1;
else {
// Max element appeared morethan 1nce
// Hill sequence isn't possible
if (freq[max] >= 2)
flag = -1;
// Hill sequence is possible
else
flag = 1;
}
// Print favourable sequence if flag==1
// Hill sequence is possible
if (flag == 1) {
foreach (KeyValuePair<int, int> i in
freq) {
// If an element's freq==1
if (i.Value == 1)
descending.Add(i.Key);
else {
// If an element's freq==2
descending.Add(i.Key);
ascending.Add(i.Key);
}
}
descending.Sort();
ascending.Sort();
ascending.Reverse();
for (int i = 0; i < descending.Count; i++)
Console.Write(descending[i] + " ");
for (int i = 0; i < ascending.Count; i++)
Console.Write(ascending[i] + " ");
}
else {
Console.WriteLine("Not Possible!");
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 5;
int[] arr = new int[n];
arr[0] = 5;
arr[1] = 7;
arr[2] = 2;
arr[3] = 1;
arr[4] = 2;
find(arr, n);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
function find(arr, n)
{
// Flag will indicate whether
// sequence is possible or not
let flag = 0;
let freq = new Map();
let a = [];
for (let i = 0; i < n; i++) {
a.push(arr[i]);
if (freq.has(arr[i]))
freq.set(arr[i], freq.get(arr[i]) + 1);
else
freq.set(arr[i], 1)
}
// Max element in <a>
let max = Math.max([...a]);
// Store only unique elements count
let freqsum = 0;
// If any element having freq more than 2
for (let [key, x] of freq) {
// Hill sequence isn't possible
if (x >= 3)
flag = -1;
}
let ascending = [], descending = [];
// Counting all distinct elements only
for (let [key, x] of freq) {
// Having freq more than 1 should
// be count only 1'nce
if (x > 1)
freqsum += 1;
else
freqsum += x;
}
// All elements are distinct
// Hill sequence is possible
if (a.length == freqsum)
flag = 1;
else {
// Max element appeared morethan 1nce
// Hill sequence isn't possible
if (freq[max] >= 2)
flag = -1;
// Hill sequence is possible
else
flag = 1;
}
// Print favourable sequence if flag==1
// Hill sequence is possible
if (flag == 1) {
for (let [key, x] of freq) {
// If an element's freq==1
if (x == 1)
descending.push(key);
else {
// If an element's freq==2
descending.push(key);
ascending.push(key);
}
}
descending.sort(function (a, b) { return a - b })
ascending.sort(function (a, b) { return b - a })
for (let x of descending)
document.write(x + " ")
for (let x of ascending)
document.write(x + " ")
}
else {
document.write("Not Possible!" + '<br>');
}
}
// Driver Code
let n = 5;
let arr = [5, 7, 2, 1, 2];
find(arr, n);
// This code is contributed by Potta Lokesh
</script>
Producción:
1 2 5 7 2
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por madhav_mohan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA