Reorganizar los números en una array de manera que no haya dos números adyacentes iguales

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: 

  1. 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.
  2. 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 }
  3. 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.
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *