Dada una array arr[] , el objetivo es contar el número de inversiones en todas las sub-arrays. Una inversión es un par de índices i y j tales que i > j y arr[i] < arr[j] . Un subarreglo del índice x al y (x<= y) consiste en el elemento arr[x], arr[x+1], …, arr[y] . La array arr[] también puede contener elementos repetidos.
Ejemplos:
Entrada : arr[] = {3, 6, 1, 6, 5, 3, 9}
Salida :
0 0 2 2 4 7 7
0 0 1 1 3 6 6
0 0 0 0 1 3 3
0 0 0 0 1 3 3
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Explicación :
el elemento en la i-ésima fila y la j-ésima columna de la salida indica el número de inversiones del índice i al j (inclusivo). Considere i = 1 y j = 4 (suponiendo indexación basada en 0), el número de inversiones en el subarreglo {6, 1, 6, 5} es 3. Los pares de elementos son (6, 1), (6, 5) y (6, 5) (del segundo 6).Entrada : arr[] = {3, 2, 1}
Salida :
0 1 3
0 0 1
0 0 0
Explicación :
Del índice 0 al 1 hay 1 inversión, del índice 2 al 3 hay 1 inversión y del índice 0 al 2 hay 3 inversiones. La i-ésima fila y la j-ésima columna de la salida es 0 si i >= j.
Enfoque ingenuo: un enfoque ingenuo es generar todos los subconjuntos posibles y contar el número de inversiones en cada uno de los subconjuntos.
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;
// Function to count the number of
// inversions in all the sub-arrays
void findSubarrayInversions(int arr[], int n)
{
int inversions[n][n];
// Initializing the inversion count
// of each subarray to 0
// inversions[i][j] will denote
// the number of inversions
// from index i to index j inclusive
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
inversions[i][j] = 0;
}
}
// Generating all subarray
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int ans = 0;
// counting the number of inversions
// for a subarray
for (int x = i; x <= j; x++) {
for (int y = x; y <= j; y++) {
if (arr[x] > arr[y])
ans++;
}
}
inversions[i][j] = ans;
}
}
// Printing the number of inversions
// of all subarrays
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << inversions[i][j] << " ";
}
cout << "\n";
}
}
// Driver Code
int main()
{
// Given Input
int n = 7;
int arr[n] = { 3, 6, 1, 6, 5, 3, 9 };
// Function Call
findSubarrayInversions(arr, n);
}
Java
// Java program for the above approach
class GFG{
// Function to count the number of
// inversions in all the sub-arrays
static void findSubarrayInversions(int arr[], int n)
{
int [][]inversions = new int[n][n];
// Initializing the inversion count
// of each subarray to 0
// inversions[i][j] will denote
// the number of inversions
// from index i to index j inclusive
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
inversions[i][j] = 0;
}
}
// Generating all subarray
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
int ans = 0;
// Counting the number of inversions
// for a subarray
for(int x = i; x <= j; x++)
{
for(int y = x; y <= j; y++)
{
if (arr[x] > arr[y])
ans++;
}
}
inversions[i][j] = ans;
}
}
// Printing the number of inversions
// of all subarrays
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
System.out.print(inversions[i][j] + " ");
}
System.out.println();
}
}
// Driver Code
public static void main(String args[])
{
// Given Input
int n = 7;
int []arr = { 3, 6, 1, 6, 5, 3, 9 };
// Function Call
findSubarrayInversions(arr, n);
}
}
// This code is contributed by SoumikMondal.
Python3
# Python3 program for the above approach # Function to count the number of # inversions in all the sub-arrays def findSubarrayInversions(arr, n): inversions = [[0 for i in range(n)] for j in range(n)] # Initializing the inversion count # of each subarray to 0 # inversions[i][j] will denote # the number of inversions # from index i to index j inclusive # Generating all subarray for i in range(0, n): for j in range(0, n): ans = 0 # Counting the number of inversions # for a subarray for x in range(i, j + 1): for y in range(x, j + 1): if (arr[x] > arr[y]): ans += 1 # Print(ans) inversions[i][j] = ans # Printing the number of inversions # of all subarrays for i in range(0, n): for j in range(0, n): print(inversions[i][j], end = " ") print() # Driver Code # Given Input n = 7 arr = [ 3, 6, 1, 6, 5, 3, 9 ] # Function Call findSubarrayInversions(arr, n) # This code is contributed by amreshkumar3
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the number of
// inversions in all the sub-arrays
static void findSubarrayInversions(int []arr, int n)
{
int [,]inversions = new int[n,n];
// Initializing the inversion count
// of each subarray to 0
// inversions[i][j] will denote
// the number of inversions
// from index i to index j inclusive
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
inversions[i,j] = 0;
}
}
// Generating all subarray
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
int ans = 0;
// counting the number of inversions
// for a subarray
for (int x = i; x <= j; x++) {
for (int y = x; y <= j; y++) {
if (arr[x] > arr[y])
ans++;
}
}
inversions[i,j] = ans;
}
}
// Printing the number of inversions
// of all subarrays
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Console.Write(inversions[i,j] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main()
{
// Given Input
int n = 7;
int []arr = { 3, 6, 1, 6, 5, 3, 9 };
// Function Call
findSubarrayInversions(arr, n);
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach
// Function to count the number of
// inversions in all the sub-arrays
function findSubarrayInversions(arr, n) {
let inversions = new Array(n).fill(0).map(() => new Array(n));
// Initializing the inversion count
// of each subarray to 0
// inversions[i][j] will denote
// the number of inversions
// from index i to index j inclusive
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
inversions[i][j] = 0;
}
}
// Generating all subarray
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
let ans = 0;
// counting the number of inversions
// for a subarray
for (let x = i; x <= j; x++) {
for (let y = x; y <= j; y++) {
if (arr[x] > arr[y])
ans++;
}
}
inversions[i][j] = ans;
}
}
// Printing the number of inversions
// of all subarrays
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
document.write(inversions[i][j] + " ");
}
document.write("<br>");
}
}
// Driver Code
// Given Input
let n = 7;
let arr = [3, 6, 1, 6, 5, 3, 9];
// Function Call
findSubarrayInversions(arr, n);
</script>
Producción:
0 0 2 2 4 7 7 0 0 1 1 3 6 6 0 0 0 0 1 3 3 0 0 0 0 1 3 3 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el método anterior se puede optimizar un poco usando el método que se proporciona aquí para encontrar el número de inversiones en un subarreglo. Primero vea algunas observaciones para resolver este problema:
Primero cree una array 2d mayor[][] , donde mayor[i][j] denota el número de elementos en el rango i a j que son mayores que arr[i]. Itere sobre la array y para cada elemento, encuentre el número de elementos a su derecha que son menores que el elemento. Esto se puede hacer usando un enfoque ingenuo en O (N ^ 2). Ahora, para encontrar el número de inversiones en un rango, digamos de x a y, la respuesta será mayor[x][y] + mayor[x+1][y] + … + mayor[y-1][y] + mayor [y][y].
Con la tabla mayor[][] , este valor se puede calcular en O(n) para cada subarreglo, lo que da como resultado una complejidad de O(n^3) . (Hay O(n^2) subarreglo, y toma O(n) tiempo para calcular el número de inversiones en cada subarreglo). Para encontrar este valor en O(1) cada vez, cree una tabla de suma de prefijos a partir de la tabla mayor[][] , donde prefijo[i][j] denota el valor de mayor[0][j] + mayor[1][j ] + … + mayor[i][j]. Esta tabla también se puede construir en tiempo O(N^2) . Ahora la respuesta para cada subarreglo de x a y (inclusive) seríaprefijo[y][y] – prefijo[x-1][y] si x >= 1 y prefijo[y][y] si x = 0.
Siga el siguiente paso para resolver este problema:
- Inicializar arreglos mayor[][] para almacenar donde mayor[i][j] denota el número de elementos en el rango i a j que son mayores que arr[i], prefijo[][] para almacenar la suma de prefijos para el subarreglo y inversiones[][] para almacenar el número de inversiones.
- Iterar en un rango [0, N-1] usando una variable i :
- Iterar en un rango [i+1, N-1] usando una variable j:
- Actualizar mayor[i][j] como mayor[i][j-1]
- Si arr[i] es mayor que arr[j], entonces Incrementa mayor[i][j] en 1.
- Iterar en un rango [i+1, N-1] usando una variable j:
- Iterar en un rango [0, N-1] usando una variable i :
- Actualizar prefijo[0][j] como mayor[0][j]
- Iterar en un rango [1, N-1] usando una variable j y actualizar el prefijo [i] [j] como prefijo [i-1] [j] + mayor [i] [j].
- Iterar en un rango [0, N-1] usando una variable i :
- Iterar en un rango [i, N-1] usando una variable j:
- Si i = 0, actualice las inversiones [i] [j] como prefijo [j] [j]
- De lo contrario, actualice inversiones[i][j] como prefijo[j][j] + prefijo[i-1][j].
- Iterar en un rango [i, N-1] usando una variable j:
- Después de completar los pasos anteriores, imprima la array de inversiones[][] como respuesta.
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;
// Function to count the number of
// inversions in all the sub-arrays
void findSubarrayInversions(int arr[], int n)
{
int greater[n][n];
int prefix[n][n];
int inversions[n][n];
// Initializing the arrays to 0
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
greater[i][j] = 0;
prefix[i][j] = 0;
inversions[i][j] = 0;
}
}
// For each pair of indices i and j
// calculating the number of elements
// from i to j inclusive which are
// greater than arr[i]
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
greater[i][j] = greater[i][j - 1];
if (arr[i] > arr[j])
greater[i][j]++;
}
}
// Building the prefix table.
// Prefix[i][j] denotes the sum of
// greater[0][j], greater[1][j] ... greater[i][j]
for (int j = 0; j < n; j++) {
prefix[0][j] = greater[0][j];
for (int i = 1; i < n; i++) {
prefix[i][j] = prefix[i - 1][j] + greater[i][j];
}
}
// Calculating the inversion count for
// each subarray using the prefix table
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == 0)
inversions[i][j] = prefix[j][j];
else
inversions[i][j] = prefix[j][j]
- prefix[i - 1][j];
}
}
// Printing the values of the number
// of inversions in each subarray
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << inversions[i][j] << " ";
}
cout << "\n";
}
}
// Driver Code
int main()
{
// Given Input
int n = 7;
int arr[n] = { 3, 6, 1, 6, 5, 3, 9 };
// Function Call
findSubarrayInversions(arr, n);
}
Python3
# Python3 program for the above approach # Function to count the number of # inversions in all the sub-arrays def findSubarrayInversions(arr, n): # Initializing the arrays to 0 greater = [[0 for i in range(n)] for j in range(n)] prefix = [[0 for i in range(n)] for j in range(n)] inversions = [[0 for i in range(n)] for j in range(n)] # For each pair of indices i and j # calculating the number of elements # from i to j inclusive which are # greater than arr[i] for i in range(0, n): for j in range(i + 1, n): greater[i][j] = greater[i][j - 1] if (arr[i] > arr[j]): greater[i][j] += 1 # Building the prefix table. # Prefix[i][j] denotes the sum of # greater[0][j], greater[1][j] ... greater[i][j] for j in range(0, n): prefix[0][j] = greater[0][j] for i in range(1, n): prefix[i][j] = (prefix[i - 1][j] + greater[i][j]) # Calculating the inversion count for # each subarray using the prefix table for i in range(0, n): for j in range(i, n): if (i == 0): inversions[i][j] = prefix[j][j] else: inversions[i][j] = (prefix[j][j] - prefix[i - 1][j]) # Printing the values of the number # of inversions in each subarray for i in range(0, n): for j in range(0, n): print(inversions[i][j], end = " ") print() # Driver Code # Given Input n = 7 arr = [ 3, 6, 1, 6, 5, 3, 9 ] # Function Call findSubarrayInversions(arr, n) # This code is contributed by amreshkumar3
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// inversions in all the sub-arrays
function findSubarrayInversions(arr, n) {
let greater = new Array(n).fill(0).map(() => new Array(n).fill(0));
let prefix = new Array(n).fill(0).map(() => new Array(n).fill(0));
let inversions = new Array(n).fill(0).map(() => new Array(n).fill(0));
// Initializing the arrays to 0
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
greater[i][j] = 0;
prefix[i][j] = 0;
inversions[i][j] = 0;
}
}
// For each pair of indices i and j
// calculating the number of elements
// from i to j inclusive which are
// greater than arr[i]
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
greater[i][j] = greater[i][j - 1];
if (arr[i] > arr[j]) greater[i][j]++;
}
}
// Building the prefix table.
// Prefix[i][j] denotes the sum of
// greater[0][j], greater[1][j] ... greater[i][j]
for (let j = 0; j < n; j++) {
prefix[0][j] = greater[0][j];
for (let i = 1; i < n; i++) {
prefix[i][j] = prefix[i - 1][j] + greater[i][j];
}
}
// Calculating the inversion count for
// each subarray using the prefix table
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
if (i == 0) inversions[i][j] = prefix[j][j];
else inversions[i][j] = prefix[j][j] - prefix[i - 1][j];
}
}
// Printing the values of the number
// of inversions in each subarray
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
document.write(inversions[i][j] + " ");
}
document.write("<br>");
}
}
// Driver Code
// Given Input
let n = 7;
let arr = [3, 6, 1, 6, 5, 3, 9];
// Function Call
findSubarrayInversions(arr, n);
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
0 0 2 2 4 7 7 0 0 1 1 3 6 6 0 0 0 0 1 3 3 0 0 0 0 1 3 3 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(N 2 )
Notas-
- Se puede ahorrar algo de espacio construyendo la tabla de prefijo[][] encima de la tabla mayor[][], pero el orden seguirá siendo el mismo.
- No es posible obtener un rendimiento mejor que O(N^2) si desea encontrar el recuento exacto de inversiones en todos los subarreglos, ya que el número de subarreglos siempre es O(N^2).