Dada una array arr[] de tamaño N , donde arr[i] denota el número de elementos de la izquierda que son mayores que el i -ésimo elemento en la permutación original. La tarea es encontrar la permutación original de [1, N] para la cual la array de inversión dada arr[] es válida.
Ejemplos:
Entrada: arr[] = {0, 1, 1, 0, 3}
Salida: 4 1 3 5 2
Explicación:
La permutación original es ans[] = {4, 1, 3, 5, 2}
ans[0] = 4.
ans[1] = 1. Dado que {4} existe a su izquierda, que excede 1, arr[1] = 1 es válido.
ans[2] = 3. Dado que {4} existe a su izquierda, que excede 3, arr[2] = 1 es válido.
ans[3] = 5. Dado que ningún elemento a su izquierda excede 5, arr[3] = 0 es válido.
ans[4] = 2. Dado que {4, 3, 5} existe a su izquierda, que excede a 2, arr[4] = 3 es válido.Entrada: arr[] = {0, 1, 2}
Salida: 3 2 1
Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones de N número y, para cada permutación, verificar si sus elementos satisfacen las inversiones dadas por la array arr[] . Si se encuentra tal permutación, imprímala.
Complejidad temporal: O(N!)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar un árbol de segmentos . Siga los pasos a continuación para resolver el problema:
- Cree un árbol de segmentos de tamaño N e inicialice todos los Nodes hoja con valor 1 .
- Recorre la array dada de derecha a izquierda. Por ejemplo, si el índice actual es N – 1 , es decir, no se visita ninguno de los elementos. Entonces, el arr[i] es el número de elementos que deben ser mayores que el elemento que debe estar en esta posición. Entonces, la respuesta para este elemento es el (N – arr[N – 1]) el elemento en el árbol de segmentos corresponde a ese elemento. Después de eso, marque ese elemento como 0 para evitar que se vuelva a contar.
- De manera similar, busque (i + 1 – arr [i]) el elemento en el árbol de segmentos, para cada i desde (N – 1) hasta 0 .
- Después de encontrar la respuesta para arr[i] , deje que sea temp , guárdelo en alguna array ans[] y actualice el Node que tiene índice temp con 0 .
- Finalmente, imprima la array de respuesta ans[] en orden inverso a la permutación original.
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;
const int MAXX = 100;
// Declaring segment tree
int st[4 * MAXX];
// Function to initialize segment tree
// with leaves filled with ones
void build(int x, int lx, int rx)
{
// Base Case
if (rx - lx == 1) {
st[x] = 1;
return;
}
// Split into two halves
int m = (lx + rx) / 2;
// Build the left subtree
build(x * 2 + 1, lx, m);
// Build the right subtree
build(x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1]
+ st[x * 2 + 2];
return;
}
// Function to make index x to 0
// and then update segment tree
void update(int i, int x,
int lx, int rx)
{
// Base Case
if (rx - lx == 1) {
st[x] = 0;
return;
}
// Split into two halves
int m = (lx + rx) / 2;
// Update Query
if (i < m)
update(i, x * 2 + 1, lx, m);
else
update(i, x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1]
+ st[x * 2 + 2];
return;
}
// Function to find the Kth element
int getans(int x, int lx, int rx,
int k, int n)
{
// Base Condition
if (rx - lx == 1) {
if (st[x] == k)
return lx;
return n;
}
// Split into two halves
int m = (lx + rx) / 2;
// Check if kth one is in left subtree
// or right subtree of current node
if (st[x * 2 + 1] >= k)
return getans(x * 2 + 1,
lx, m, k, n);
else
return getans(x * 2 + 2, m,
rx, k - st[x * 2 + 1],
n);
}
// Function to generate the original
// permutation
void getPermutation(int inv[], int n)
{
// Build segment tree
build(0, 0, n);
// Stores the original permutation
vector<int> ans;
for (int i = n - 1; i >= 0; i--) {
// Find kth one
int temp = getans(0, 0, n,
st[0] - inv[i], n);
// Answer for arr[i]
ans.push_back(temp + 1);
// Setting found value back to 0
update(max(0, temp), 0, 0, n);
}
// Print the permutation
for (int i = n - 1; i >= 0; i--)
cout << ans[i] << " ";
return;
}
// Driver Code
int main()
{
// Given array
int inv[] = { 0, 1, 1, 0, 3 };
// Length of the given array
int N = sizeof(inv) / sizeof(inv[0]);
// Function Call
getPermutation(inv, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int MAXX = 100;
// Declaring segment tree
static int []st = new int[4 * MAXX];
// Function to initialize segment tree
// with leaves filled with ones
static void build(int x, int lx, int rx)
{
// Base Case
if (rx - lx == 1)
{
st[x] = 1;
return;
}
// Split into two halves
int m = (lx + rx) / 2;
// Build the left subtree
build(x * 2 + 1, lx, m);
// Build the right subtree
build(x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1] + st[x * 2 + 2];
return;
}
// Function to make index x to 0
// and then update segment tree
static void update(int i, int x,
int lx, int rx)
{
// Base Case
if (rx - lx == 1)
{
st[x] = 0;
return;
}
// Split into two halves
int m = (lx + rx) / 2;
// Update Query
if (i < m)
update(i, x * 2 + 1, lx, m);
else
update(i, x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1] + st[x * 2 + 2];
return;
}
// Function to find the Kth element
static int getans(int x, int lx, int rx,
int k, int n)
{
// Base Condition
if (rx - lx == 1)
{
if (st[x] == k)
return lx;
return n;
}
// Split into two halves
int m = (lx + rx) / 2;
// Check if kth one is in left subtree
// or right subtree of current node
if (st[x * 2 + 1] >= k)
return getans(x * 2 + 1,
lx, m, k, n);
else
return getans(x * 2 + 2, m, rx,
k - st[x * 2 + 1], n);
}
// Function to generate the original
// permutation
static void getPermutation(int inv[], int n)
{
// Build segment tree
build(0, 0, n);
// Stores the original permutation
Vector<Integer> ans = new Vector<Integer>();
for(int i = n - 1; i >= 0; i--)
{
// Find kth one
int temp = getans(0, 0, n,
st[0] - inv[i], n);
// Answer for arr[i]
ans.add(temp + 1);
// Setting found value back to 0
update(Math.max(0, temp), 0, 0, n);
}
// Print the permutation
for(int i = n - 1; i >= 0; i--)
System.out.print(ans.get(i) + " ");
return;
}
// Driver Code
public static void main(String args[])
{
// Given array
int inv[] = { 0, 1, 1, 0, 3 };
// Length of the given array
int N = inv.length;
// Function Call
getPermutation(inv, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 program for the above approach MAXX = 100 # Declaring segment tree st = [0] * (4 * MAXX) # Function to initialize segment tree # with leaves filled with ones def build(x, lx, rx): # Base Case if (rx - lx == 1): st[x] = 1 return # Split into two halves m = (lx + rx) // 2 # Build the left subtree build(x * 2 + 1, lx, m) # Build the right subtree build(x * 2 + 2, m, rx) # Combining both left and right # subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2] return # Function to make index x to 0 # and then update segment tree def update(i, x, lx, rx): # Base Case if (rx - lx == 1): st[x] = 0 return # Split into two halves m = (lx + rx) // 2 # Update Query if (i < m): update(i, x * 2 + 1, lx, m) else: update(i, x * 2 + 2, m, rx) # Combining both left and right # subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2] return # Function to find the Kth element def getans(x, lx, rx, k, n): # Base Condition if (rx - lx == 1): if (st[x] == k): return lx return n # Split into two halves m = (lx + rx) // 2 # Check if kth one is in left subtree # or right subtree of current node if (st[x * 2 + 1] >= k): return getans(x * 2 + 1, lx, m, k, n) else: return getans(x * 2 + 2, m, rx, k - st[x * 2 + 1], n) # Function to generate the original # permutation def getPermutation(inv, n): # Build segment tree build(0, 0, n) # Stores the original permutation ans = [] for i in range(n - 1, -1, -1): # Find kth one temp = getans(0, 0, n, st[0] - inv[i], n) # Answer for arr[i] ans.append(temp + 1) # Setting found value back to 0 update(max(0, temp), 0, 0, n) # Print the permutation for i in range(n - 1, -1, -1): print(ans[i], end = " ") return # Driver Code if __name__ == '__main__': # Given array inv = [ 0, 1, 1, 0, 3 ] # Length of the given array N = len(inv) # Function Call getPermutation(inv, N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int MAXX = 100;
// Declaring segment tree
static int []st = new int[4 * MAXX];
// Function to initialize segment tree
// with leaves filled with ones
static void build(int x, int lx, int rx)
{
// Base Case
if (rx - lx == 1)
{
st[x] = 1;
return;
}
// Split into two halves
int m = (lx + rx) / 2;
// Build the left subtree
build(x * 2 + 1, lx, m);
// Build the right subtree
build(x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1] + st[x * 2 + 2];
return;
}
// Function to make index x to 0
// and then update segment tree
static void update(int i, int x,
int lx, int rx)
{
// Base Case
if (rx - lx == 1)
{
st[x] = 0;
return;
}
// Split into two halves
int m = (lx + rx) / 2;
// Update Query
if (i < m)
update(i, x * 2 + 1, lx, m);
else
update(i, x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1] + st[x * 2 + 2];
return;
}
// Function to find the Kth element
static int getans(int x, int lx, int rx,
int k, int n)
{
// Base Condition
if (rx - lx == 1)
{
if (st[x] == k)
return lx;
return n;
}
// Split into two halves
int m = (lx + rx) / 2;
// Check if kth one is in left subtree
// or right subtree of current node
if (st[x * 2 + 1] >= k)
return getans(x * 2 + 1,
lx, m, k, n);
else
return getans(x * 2 + 2, m, rx,
k - st[x * 2 + 1], n);
}
// Function to generate the original
// permutation
static void getPermutation(int []inv, int n)
{
// Build segment tree
build(0, 0, n);
// Stores the original permutation
List<int> ans = new List<int>();
for(int i = n - 1; i >= 0; i--)
{
// Find kth one
int temp = getans(0, 0, n,
st[0] - inv[i], n);
// Answer for arr[i]
ans.Add(temp + 1);
// Setting found value back to 0
update(Math.Max(0, temp), 0, 0, n);
}
// Print the permutation
for(int i = n - 1; i >= 0; i--)
Console.Write(ans[i] + " ");
return;
}
// Driver Code
public static void Main(String []args)
{
// Given array
int []inv = { 0, 1, 1, 0, 3 };
// Length of the given array
int N = inv.Length;
// Function Call
getPermutation(inv, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
let MAXX = 100;
// Declaring segment tree
let st = new Array(4 * MAXX);
// Function to initialize segment tree
// with leaves filled with ones
function build(x, lx, rx)
{
// Base Case
if (rx - lx == 1)
{
st[x] = 1;
return;
}
// Split into two halves
let m = parseInt((lx + rx) / 2, 10);
// Build the left subtree
build(x * 2 + 1, lx, m);
// Build the right subtree
build(x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1] + st[x * 2 + 2];
return;
}
// Function to make index x to 0
// and then update segment tree
function update(i, x, lx, rx)
{
// Base Case
if (rx - lx == 1)
{
st[x] = 0;
return;
}
// Split into two halves
let m = parseInt((lx + rx) / 2, 10);
// Update Query
if (i < m)
update(i, x * 2 + 1, lx, m);
else
update(i, x * 2 + 2, m, rx);
// Combining both left and right
// subtree to parent node
st[x] = st[x * 2 + 1] + st[x * 2 + 2];
return;
}
// Function to find the Kth element
function getans(x, lx, rx, k, n)
{
// Base Condition
if (rx - lx == 1)
{
if (st[x] == k)
return lx;
return n;
}
// Split into two halves
let m = parseInt((lx + rx) / 2, 10);
// Check if kth one is in left subtree
// or right subtree of current node
if (st[x * 2 + 1] >= k)
return getans(x * 2 + 1, lx, m, k, n);
else
return getans(x * 2 + 2, m, rx,
k - st[x * 2 + 1], n);
}
// Function to generate the original
// permutation
function getPermutation(inv, n)
{
// Build segment tree
build(0, 0, n);
// Stores the original permutation
let ans = [];
for(let i = n - 1; i >= 0; i--)
{
// Find kth one
let temp = getans(0, 0, n,
st[0] - inv[i], n);
// Answer for arr[i]
ans.push(temp + 1);
// Setting found value back to 0
update(Math.max(0, temp), 0, 0, n);
}
// Print the permutation
for(let i = n - 1; i >= 0; i--)
document.write(ans[i] + " ");
return;
}
// Driver code
// Given array
let inv = [ 0, 1, 1, 0, 3 ];
// Length of the given array
let N = inv.length;
// Function Call
getPermutation(inv, N);
// This code is contributed by suresh07
</script>
Producción:
4 1 3 5 2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Tema relacionado: Árbol de segmentos