Dada una array de enteros. La tarea es reorganizar los elementos de la array de manera que no haya dos elementos adyacentes iguales en la array.
Ejemplos:
Input: arr[] = {1, 1, 1, 2, 2, 2}
Output: {2, 1, 2, 1, 2, 1}
Input: arr[] = {1, 1, 1, 1, 2, 2, 3, 3}
Output: {1, 3, 1, 3, 2, 1, 2, 1}
La idea es poner primero el elemento de frecuencia más alta (un enfoque codicioso). Usamos una cola de prioridad (o Binary Max Heap) y colocamos todos los elementos y los ordenamos por sus frecuencias (el elemento de mayor frecuencia en la raíz). Luego, uno por uno, tomamos el elemento de mayor frecuencia del montón y lo agregamos al resultado. Después de agregar, disminuimos la frecuencia del elemento y lo sacamos temporalmente de la cola de prioridad para que no se seleccione la próxima vez.
Tenemos que seguir los pasos para solucionar este problema, son:
- Cree un Priority_queue o max_heap, pq que almacene elementos y sus frecuencias.
…… Priority_queue o max_heap se construye sobre la base de la frecuencia de los elementos. - Cree una clave temporal que se usará como el elemento visitado anteriormente (el elemento anterior en la array resultante. Inicialícela { num = -1, freq = -1 }
- Mientras que pq no está vacío.
- Haga estallar un elemento y agréguelo al resultado.
- Disminuya la frecuencia del elemento reventado en ‘1’.
- Vuelva a colocar el elemento anterior en la cola de prioridad si su frecuencia es > ‘0’.
- Haga que el elemento actual sea el elemento anterior para la siguiente iteración.
- Si la longitud de la string resultante y la original no son iguales, escriba «no es posible». De lo contrario, imprima el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program to rearrange numbers in
// an Array such that no two numbers are
// adjacent
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange numbers in array such
// that no two adjacent numbers are same
void rearrangeArray(int arr[], int N)
{
// Store frequencies of all elements
// of the array
map<int, int>mp, visited;
for(int i = 0; i < N; i++)
{
mp[arr[i]]++;
}
priority_queue<pair<int, int>>pq;
// Adding high freq elements
// in descending order
for(int i = 0; i < N ; i++)
{
int val = arr[i];
if (mp[val] > 0 and visited[val] != 1)
{
pq.push({mp[val], val});
}
visited[val] = 1;
}
// 'result[]' that will store resultant value
vector<int>result(N);
// Work as the previous visited element
// initial previous element will be ( '-1' and
// it's frequency wiint also be '-1' )
pair<int, int>prev = { -1, -1 };
int l = 0;
// Traverse queue
while (pq.size() != 0)
{
// Pop top element from queue and add it
// to result
pair<int,int>k = pq.top();
pq.pop();
result[l] = k.second;
// If frequency of previous element is less
// than zero that means it is useless, we
// need not to push it
if (prev.first > 0)
{
pq.push(prev);
}
// Make current element as the previous
// decrease frequency by 'one'
k.first--;
prev = k;
l++;
}
for(auto it : result)
{
if (it == 0)
{
// If found 0, No valid result
// array possible
cout << "Not valid Array" << endl;
return;
}
}
for(auto it : result)
{
cout << it << ", ";
}
}
// Driver Code
int main()
{
int A[] = { 1, 1, 1, 1, 2, 2, 3, 3 };
// Size of the array
int N = sizeof(A) / sizeof(A[0]);
rearrangeArray(A, N);
}
// This code is contributed by koulick_sadhu
Java
// Java Program to rearrange numbers in an Array
// such that no two numbers are adjacent
import java.util.Comparator;
import java.util.PriorityQueue;
// Comparator class to sort in descending order
class KeyComparator implements Comparator<Key>
{
// Overriding compare()method of Comparator
public int compare(Key k1, Key k2)
{
if (k1.freq < k2.freq)
return 1;
else if (k1.freq > k2.freq)
return -1;
return 0;
}
}
// Object of num and its freq
class Key
{
int freq; // store frequency of character
int num;
Key(int freq, int num)
{
this.freq = freq;
this.num = num;
}
}
public class GFG
{
// Function to rearrange numbers in array such
// that no two adjacent numbers are same
static void rearrangeArray(int[] arr)
{
int n = arr.length;
// Store frequencies of all elements
// of the array
int[] count = new int[10000];
int visited[] = new int[10000];
for (int i = 0; i < n; i++)
count[arr[i]]++;
// Insert all characters with their frequencies
// into a priority_queue
PriorityQueue<Key> pq
= new PriorityQueue<>(new KeyComparator());
// Adding high freq elements in descending order
for (int i = 0; i < n; i++)
{
int val = arr[i];
if (count[val] > 0 && visited[val] != 1)
pq.add(new Key(count[val], val));
visited[val] = 1;
}
// 'result[]' that will store resultant value
int result[] = new int[n];
// work as the previous visited element
// initial previous element will be ( '-1' and
// it's frequency will also be '-1' )
Key prev = new Key(-1, -1);
// Traverse queue
int l = 0;
while (pq.size() != 0)
{
// pop top element from queue and add it
// to result
Key k = pq.peek();
pq.poll();
result[l] = k.num;
// If frequency of previous element is less
// than zero that means it is useless, we
// need not to push it
if (prev.freq > 0)
pq.add(prev);
// make current element as the previous
// decrease frequency by 'one'
(k.freq)--;
prev = k;
l++;
}
// If length of the resultant array and original
// array is not same then the array is not valid
if (l != result.length)
{
System.out.println(" Not valid Array ");
}
// Otherwise Print the result array
else
{
for (int i : result)
{
System.out.print(i + " ");
}
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = new int[] { 1, 1, 1, 1, 2, 2, 3, 3 };
rearrangeArray(arr);
}
}
Python3
# Python3 program to rearrange numbers in
# an Array such that no two numbers are
# adjacent
# Function to rearrange numbers in array such
# that no two adjacent numbers are same
def rearrangeArray(arr, N) :
# Store frequencies of all elements
# of the array
mp = {}
visited = {}
for i in range(N) :
if(arr[i] in mp) :
mp[arr[i]] += 1
else :
mp[arr[i]] = 1
pq = []
# Adding high freq elements
# in descending order
for i in range(N) :
val = arr[i]
if((val in mp) and ((val not in visited) or (visited[val] != 1))) :
pq.append([mp[val], val])
visited[val] = 1
pq.sort()
pq.reverse()
# 'result[]' that will store resultant value
result = [0]*N
# Work as the previous visited element
# initial previous element will be ( '-1' and
# it's frequency wiint also be '-1' )
prev = [-1, -1]
l = 0
# Traverse queue
while (len(pq) != 0) :
# Pop top element from queue and add it
# to result
k = pq[0]
pq.pop(0)
result[l] = k[1]
# If frequency of previous element is less
# than zero that means it is useless, we
# need not to push it
if (prev[0] > 0) :
pq.append(prev)
pq.sort()
pq.reverse()
# Make current element as the previous
# decrease frequency by 'one'
prev = [k[0] - 1, k[1]]
l += 1
for it in result :
if (it == 0) :
# If found 0, No valid result
# array possible
print("Not valid Array")
return
for it in result :
print(it , end = " ")
A = [ 1, 1, 1, 1, 2, 2, 3, 3 ]
# Size of the array
N = len(A)
rearrangeArray(A, N)
#This code is contributed by divyesh072019.
C#
// C# program to rearrange numbers in
// an Array such that no two numbers are
// adjacent
using System;
using System.Collections.Generic;
class GFG{
// Function to rearrange numbers in array such
// that no two adjacent numbers are same
static void rearrangeArray(int[] arr, int N)
{
// Store frequencies of all elements
// of the array
Dictionary<int, int> mp = new Dictionary<int, int>();
Dictionary<int, int> visited = new Dictionary<int, int>();
for(int i = 0; i < N; i++)
{
if(mp.ContainsKey(arr[i]))
{
mp[arr[i]] += 1;
}
else{
mp[arr[i]] = 1;
}
}
List<Tuple<int, int>> pq = new List<Tuple<int,int>>();
// Adding high freq elements
// in descending order
for(int i = 0; i < N ; i++)
{
int val = arr[i];
if (mp.ContainsKey(val) && (!visited.ContainsKey(val) || visited[val] != 1))
{
pq.Add(new Tuple<int,int>(mp[val], val));
}
visited[val] = 1;
}
pq.Sort();
pq.Reverse();
// 'result[]' that will store resultant value
int[] result = new int[N];
// Work as the previous visited element
// initial previous element will be ( '-1' and
// it's frequency wiint also be '-1' )
Tuple<int, int> prev = new Tuple<int,int>( -1, -1 );
int l = 0;
// Traverse queue
while (pq.Count != 0)
{
// Pop top element from queue and add it
// to result
Tuple<int,int> k = pq[0];
pq.RemoveAt(0);
result[l] = k.Item2;
// If frequency of previous element is less
// than zero that means it is useless, we
// need not to push it
if (prev.Item1 > 0)
{
pq.Add(prev);
pq.Sort();
pq.Reverse();
}
// Make current element as the previous
// decrease frequency by 'one'
prev = new Tuple<int,int>(k.Item1 - 1, k.Item2);
l++;
}
foreach(int it in result)
{
if (it == 0)
{
// If found 0, No valid result
// array possible
Console.WriteLine("Not valid Array");
return;
}
}
foreach(int it in result)
{
Console.Write(it + " ");
}
}
// Driver code
static void Main()
{
int[] A = { 1, 1, 1, 1, 2, 2, 3, 3 };
// Size of the array
int N = A.Length;
rearrangeArray(A, N);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to rearrange numbers in
// an Array such that no two numbers are
// adjacent
// Function to rearrange numbers in array such
// that no two adjacent numbers are same
function rearrangeArray(arr, N)
{
// Store frequencies of all elements
// of the array
var mp = new Map();
var visited = new Map();
for(var i = 0; i < N; i++)
{
if(mp.has(arr[i]))
mp.set(arr[i], mp.get(arr[i])+1)
else
mp.set(arr[i], 1)
}
var pq = [];
// Adding high freq elements
// in descending order
for(var i = 0; i < N ; i++)
{
var val = arr[i];
if (mp.get(val) > 0 && visited[val] != 1)
{
pq.push([mp.get(val), val]);
}
visited[val] = 1;
}
pq.sort();
// 'result[]' that will store resultant value
var result = Array(N).fill(0);
// Work as the previous visited element
// initial previous element will be ( '-1' and
// it's frequency wiint also be '-1' )
var prev = [-1, -1];
var l = 0;
// Traverse queue
while (pq.length != 0)
{
// Pop top element from queue and add it
// to result
var k = pq[pq.length-1];
pq.pop();
result[l] = k[1];
// If frequency of previous element is less
// than zero that means it is useless, we
// need not to push it
if (prev[0] > 0)
{
pq.push(prev);
}
pq.sort();
// Make current element as the previous
// decrease frequency by 'one'
k[0]--;
prev = k;
l++;
}
for(var it of result)
{
if (it == 0)
{
// If found 0, No valid result
// array possible
document.write("Not valid Array" + "<br>");
return;
}
}
for(var it of result)
{
document.write(it + " ");
}
}
// Driver Code
var A = [1, 1, 1, 1, 2, 2, 3, 3];
// Size of the array
var N = A.length;
rearrangeArray(A, N);
// This code is contributed by rutvik_56.
</script>
Producción:
1 3 1 2 1 3 2 1
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por CajetanRodrigues y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA