Dadas dos arrays A y B de N enteros. Reordenar los elementos de B en sí mismo de tal manera que la secuencia formada por (A[i] + B[i]) % N después de reordenar sea la más pequeña lexicográficamente. La tarea es imprimir la secuencia lexicográficamente más pequeña posible.
Nota : Los elementos de la array están en el rango [0, n).
Ejemplos:
Entrada: a[] = {0, 1, 2, 1}, b[] = {3, 2, 1, 1}
Salida: 1 0 0 2
Reordenar B a {1, 3, 2, 1} para obtener el secuencia más pequeña posible.
Entrada: a[] = {2, 0, 0}, b[] = {1, 0, 2}
Salida: 0 0 2
Enfoque: El problema se puede resolver con avidez . Inicialmente, mantenga un recuento de todos los números de la array B usando hashing, y guárdelos en el conjunto en C++ , de modo que las operaciones lower_bound() [ Para verificar un elemento ] y erase() [ Para borrar un elemento ] se puedan realizar en tiempo logarítmico.
Para cada elemento de la array, busque un número igual o mayor que na[i] usando la función lower_bound . Si no existen tales elementos, tome el elemento más pequeño del conjunto. Disminuya el valor en 1 en la tabla hash para el número utilizado, si el valor de la tabla hash es 0, también borre el elemento del conjunto.
Sin embargo, hay una excepción si el elemento de la array es 0, luego verifique si hay 0 al principio y luego si N, si ninguno de los dos está allí, luego tome el elemento más pequeño.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the smallest
// sequence possible
void solve(int a[], int b[], int n)
{
// Hash-table to count the
// number of occurrences of b[i]
unordered_map<int, int> mpp;
// Store the element in sorted order
// for using binary search
set<int> st;
// Iterate in the B array
// and count the occurrences and
// store in the set
for (int i = 0; i < n; i++) {
mpp[b[i]]++;
st.insert(b[i]);
}
vector<int> sequence;
// Iterate for N elements
for (int i = 0; i < n; i++) {
// If the element is 0
if (a[i] == 0) {
// Find the nearest number to 0
auto it = st.lower_bound(0);
int el = *it;
sequence.push_back(el % n);
// Decrease the count
mpp[el]--;
// Erase if no more are there
if (!mpp[el])
st.erase(el);
}
// If the element is other than 0
else {
// Find the difference
int x = n - a[i];
// Find the nearest number which can give us
// 0 on modulo
auto it = st.lower_bound(x);
// If no such number occurs then
// find the number closest to 0
if (it == st.end())
it = st.lower_bound(0);
// Get the number
int el = *it;
// store the number
sequence.push_back((a[i] + el) % n);
// Decrease the count
mpp[el]--;
// If no more appears, then erase it from set
if (!mpp[el])
st.erase(el);
}
}
for (auto it : sequence)
cout << it << " ";
}
// Driver Code
int main()
{
int a[] = { 0, 1, 2, 1 };
int b[] = { 3, 2, 1, 1 };
int n = sizeof(a) / sizeof(a[0]);
solve(a, b, n);
return 0;
}
1 0 0 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)