Tenemos una array A de n enteros que planeamos clasificar. Específicamente, queremos saber qué tan cerca está la array de ordenarse. Para lograr esto, introducimos la idea de una inversión . Una inversión en array es un par de dos índices i y j tales que i < j y A[i] > A[j] . Si nuestra array contiene una inversión, solo necesitamos intercambiar A[i] y A[j] para ordenar la array. Una array que contiene 0 inversiones está ordenada por definición.
Problema:
Dado un arreglo A de n enteros, encuentre la suma del número de inversiones en todos los subarreglos de longitud k . Para aclarar, se debe determinar el número de inversiones en cada uno de los n – k + 1 subarreglos de longitud k y sumarlos.
Entrada: La primera línea contiene dos números enteros n y k separados por espacios . La siguiente línea contiene una secuencia de n enteros separados por espacios donde el i -ésimo entero en la secuencia es A[i] .
Ejemplos:
Input : arr[] = {1 2 3 4 5 6}
k = 2
Output : 0
Input : arr[] = {1 6 7 2}
k = 3
Output : 2
There are two subarrays of size 3,
{1, 6, 7} and {6, 7, 2}. Count of
inversions in first subarray is 0
and count of inversions in second
subarray is 2. So sum is 0 + 2 = 2
Input : 8 4
12 3 14 8 15 1 4 22
Output : 14
Input : 10 5
15 51 44 44 76 50 29 88 48 50
Output : 25
[1] Enfoque ingenuo: este problema parece bastante trivial al principio, y podemos implementar fácilmente un algoritmo ingenuo para forzar la solución. Simplemente creamos una ventana de longitud k y hacemos rodar la ventana a lo largo de A , sumando el número de inversiones en la ventana en cada iteración. Para encontrar el número de inversiones, el enfoque más simple es usar dos bucles for para considerar todos los pares de elementos e incrementar un contador si el par forma una inversión.
Este enfoque es muy fácil de implementar, pero ¿es eficiente? Analicemos el algoritmo. El ciclo más externo se ejecuta n – k + 1 veces, una vez para cada k -subarreglo de A. En cada una de estas iteraciones, encontramos el número de inversiones en la ventana. Para ello, consideramos el elemento 1 y los elementos 2 , …, n , luego el elemento 2 y los elementos 3 , …, n hasta el elemento n – 1 y el elemento n . Efectivamente, estamos realizando n + (n – 1) + (n – 2) + … + 1 = n(n + 1)/2 operaciones. Por lo tanto, nuestro algoritmo realiza aproximadamente (n – k + 1)(n)(n + 1)/2operaciones que es O(n^3 – kn^2) . Dado que k puede oscilar entre 1 y n, el rendimiento en el peor de los casos para este algoritmo es O(n^3) cuando k = n/2 . ¡Podemos hacerlo mejor!
Implementación:
C++
// C++ implementation of above approach
#include <iostream>
using namespace std;
// Helper function, counts number of inversions
// via bubble sort loop
int bubble_count(int arr[], int start, int end)
{
int count = 0;
for (int i = start; i < end; i++)
{
for (int j = i + 1; j < end; j++)
{
if (arr[i] > arr[j])
{
count++;
}
}
}
return count;
}
// Inversion counting method, slides window of
// [start, end] across array
int inversion_count(int n, int k, int a[])
{
int count = 0;
for (int start = 0; start < n - k + 1; start++)
{
int end = start + k;
count += bubble_count(a, start, end);
}
return count;
}
// Driver Code
int main()
{
int n = 10;
int arr[n] = { 15, 51, 44, 44, 76,
50, 29, 88, 48, 50 };
int k = 5;
int result = inversion_count(n, k, arr);
cout << result;
return 0;
}
// This code is contributed by PrinciRaj1992
Java
public class Subarray_Inversions {
// Inversion counting method, slides window of [start,
// end] across array
static int inversion_count(int n, int k, int[] a)
{
int count = 0;
for (int start = 0; start < n - k + 1; start++) {
int end = start + k;
count += bubble_count(a, start, end);
}
return count;
}
// Helper function, counts number of inversions via
// bubble sort loop
public static int bubble_count(int[] arr, int start, int end)
{
int count = 0;
for (int i = start; i < end; i++) {
for (int j = i + 1; j < end; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
public static void main(String[] args)
{
int n = 10;
int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
int k = 5;
long result = inversion_count(n, k, arr);
System.out.println(result);
}
}
Python3
# Python3 implementation of above approach # Helper function, counts number of inversions # via bubble sort loop def bubble_count(arr, start, end): count = 0; for i in range(start, end): for j in range(i + 1, end): if (arr[i] > arr[j]): count += 1; return count; # Inversion counting method, slides window # of [start, end] across array def inversion_count(n, k, a): count = 0; for start in range(0, n - k + 1): end = start + k; count += bubble_count(a, start, end); return count; # Driver Code if __name__ == '__main__': n = 10; arr = [15, 51, 44, 44, 76, 50, 29, 88, 48, 50]; k = 5; result = inversion_count(n, k, arr); print(result); # This code is contributed by Rajput-Ji
C#
// C# implementation of above approach
using System;
public class Subarray_Inversions
{
// Inversion counting method, slides window of [start,
// end] across array
static int inversion_count(int n, int k, int[] a)
{
int count = 0;
for (int start = 0; start < n - k + 1; start++)
{
int end = start + k;
count += bubble_count(a, start, end);
}
return count;
}
// Helper function, counts number of inversions via
// bubble sort loop
public static int bubble_count(int[] arr, int start, int end)
{
int count = 0;
for (int i = start; i < end; i++)
{
for (int j = i + 1; j < end; j++)
{
if (arr[i] > arr[j])
{
count++;
}
}
}
return count;
}
// Driver code
public static void Main()
{
int n = 10;
int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
int k = 5;
long result = inversion_count(n, k, arr);
Console.WriteLine(result);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Inversion counting method, slides window of [start,
// end] across array
function inversion_count(n,k,a)
{
let count = 0;
for (let start = 0; start < n - k + 1; start++) {
let end = start + k;
count += bubble_count(a, start, end);
}
return count;
}
// Helper function, counts number of inversions via
// bubble sort loop
function bubble_count(arr,start,end)
{
let count = 0;
for (let i = start; i < end; i++) {
for (let j = i + 1; j < end; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
let n = 10;
let arr = [ 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 ];
let k = 5;
let result = inversion_count(n, k, arr);
document.write(result);
// This code is contributed by G.Sravan Kumar (171FA07058)
</script>
25
[2] Implementación basada en Mergesort: una optimización que podemos hacer es mejorar nuestro ineficiente método de conteo de inversión de tiempo cuadrático. Un enfoque podría implicar el uso de un método basado en mergesort como se describe en este artículo . Dado que esto se ejecuta en O(nlogn) , nuestro tiempo de ejecución general se reduce a O(n^2logn) , que es mejor, pero aún no podrá manejar casos en los que n = 10^6, por ejemplo.
Implementación:
Java
import java.util.*;
public class Subarray_Inversions {
// Inversion counting method, slides window of [start,
// end] across array
static int inversion_count(int n, int k, int[] a)
{
int count = 0;
for (int start = 0; start < n - k + 1; start++) {
int[] sub_array = new int[k];
for (int i = start; i < start + k; i++) {
sub_array[i - start] = a[i];
}
count += subarray_inversion_count(sub_array);
}
return count;
}
// Counts number of inversions when merging
public static long merge_inversion_count(int[] arr,
int[] left, int[] right)
{
int i = 0, j = 0, count = 0;
while (i < left.length || j < right.length) {
if (i == left.length) {
arr[i + j] = right[j];
j++;
} else if (j == right.length) {
arr[i + j] = left[i];
i++;
} else if (left[i] <= right[j]) {
arr[i + j] = left[i];
i++;
} else {
arr[i + j] = right[j];
count += left.length - i;
j++;
}
}
return count;
}
// Divide and conquer approach -- splits array and counts
// inversions via merge method
public static long subarray_inversion_count(int[] arr)
{
if (arr.length < 2)
return 0;
int m = (arr.length + 1) / 2;
int left[] = Arrays.copyOfRange(arr, 0, m);
int right[] = Arrays.copyOfRange(arr, m, arr.length);
return subarray_inversion_count(left) +
subarray_inversion_count(right) +
merge_inversion_count(arr, left, right);
}
public static void main(String[] args)
{
int n = 10;
int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
int k = 5;
long result = inversion_count(n, k, arr);
System.out.println(result);
}
}
C#
using System;
using System.Collections.Generic;
public class Subarray_Inversions {
// Inversion counting method, slides window of [start,
// end] across array
static int inversion_count(int n, int k, int[] a)
{
int count = 0;
for (int start = 0; start < n - k + 1; start++) {
int[] sub_array = new int[k];
for (int i = start; i < start + k; i++) {
sub_array[i - start] = a[i];
}
count += subarray_inversion_count(sub_array);
}
return count;
}
// Counts number of inversions when merging
public static int merge_inversion_count(int[] arr,
int[] left, int[] right)
{
int i = 0, j = 0, count = 0;
while (i < left.Length || j < right.Length) {
if (i == left.Length) {
arr[i + j] = right[j];
j++;
} else if (j == right.Length) {
arr[i + j] = left[i];
i++;
} else if (left[i] <= right[j]) {
arr[i + j] = left[i];
i++;
} else {
arr[i + j] = right[j];
count += left.Length - i;
j++;
}
}
return count;
}
// Divide and conquer approach -- splits array and counts
// inversions via merge method
public static int subarray_inversion_count(int[] arr)
{
if (arr.Length < 2)
return 0;
int m = (arr.Length + 1) / 2;
int []left = new int[m];
Array.Copy(arr, 0, left,0, m);
int []right = new int[arr.Length - m];
Array.Copy(arr, m, right,0, arr.Length - m);
return subarray_inversion_count(left) +
subarray_inversion_count(right) +
merge_inversion_count(arr, left, right);
}
public static void Main(String[] args)
{
int n = 10;
int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
int k = 5;
long result = inversion_count(n, k, arr);
Console.WriteLine(result);
}
}
// This code is contributed by Rajput-Ji
25
[3] Implementación de subarreglos superpuestos: revisemos nuestro enfoque general. Miramos la ventana [0, k) y buscamos el número de inversiones, luego miramos [1, k+1) . Hay una superposición significativa en este rango: ya hemos contado el número de inversiones en [1, k)durante la primera iteración, ¡y ahora los estamos contando de nuevo! En lugar de contar las inversiones, contemos el cambio en las inversiones de una ventana a la siguiente. Efectivamente, cambiar la ventana es simplemente agregar un elemento a la cabeza de la ventana y quitar un elemento de su cola: el cuerpo de la ventana sigue siendo el mismo. Verificar inversiones entre elementos internos sería redundante; todo lo que tenemos que hacer es sumar el número de inversiones inducidas por el nuevo elemento y restar el número de inversiones inducidas por el elemento eliminado. Ahora solo necesitamos contar el número de inversiones en la primera ventana, lo que podemos hacer en tiempo O(klogk) , y para cada una de las n – k ventanas adicionales, simplemente realizamos una iteración a través de la kelementos en la array para encontrar el cambio en el número de inversiones. Nuestro tiempo de ejecución general ahora es O(k(n – k) + klogk) = O(nk – k) que sigue siendo el peor de los casos O(n^2) .
Implementación:
Java
import java.util.*;
public class Subarray_Inversions {
// Inversion counting method, slides window of [start,
// end] across array
static long inversion_count(int n, int m, int[] arr)
{
long count = 0;
count += subarray_inversion_count_initial(Arrays.copyOfRange(arr, 0, m));
long subarray_count = subarray_inversion_count_initial(Arrays.copyOfRange(arr, 1, m));
for (int start = 1; start <= n - m; start++) {
int end = start + m - 1;
long[] ans = subarray_inversion_count(arr, start, end, subarray_count);
count += ans[0];
subarray_count = ans[1];
}
return count;
}
// start >=1; find inversion in interval [start, end)
public static long[] subarray_inversion_count(int[] arr, int start,
int end, long subarray_count)
{
int new_element = arr[end];
long count = subarray_count;
for (int i = start; i < end; i++) {
if (new_element < arr[i])
count++;
}
long totalSum = count;
int last_element = arr[start];
for (int i = start + 1; i <= end; i++) {
if (last_element > arr[i])
count--;
}
long[] ans = { totalSum, count };
return ans;
}
// Counts number of inversions when merging
public static long merge_inversion_count(int[] arr, int[] left,
int[] right)
{
int i = 0, j = 0, count = 0;
while (i < left.length || j < right.length) {
if (i == left.length) {
arr[i + j] = right[j];
j++;
} else if (j == right.length) {
arr[i + j] = left[i];
i++;
} else if (left[i] <= right[j]) {
arr[i + j] = left[i];
i++;
} else {
arr[i + j] = right[j];
count += left.length - i;
j++;
}
}
return count;
}
// Divide and conquer approach -- splits array and counts
// inversions via merge method
public static long subarray_inversion_count_initial(int[] arr)
{
if (arr.length < 2)
return 0;
int m = (arr.length + 1) / 2;
int left[] = Arrays.copyOfRange(arr, 0, m);
int right[] = Arrays.copyOfRange(arr, m, arr.length);
return subarray_inversion_count_initial(left) +
subarray_inversion_count_initial(right) +
merge_inversion_count(arr, left, right);
}
public static void main(String[] args) throws Exception
{
int n = 10;
int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
int k = 5;
long result = inversion_count(n, k, arr);
System.out.println(result);
}
}
25
[4] Implementación del árbol indexado binario:Iterar sobre cada ventana parece inevitable, por lo que el cuello de botella aquí parece ser la forma en que manejamos las ventanas. Sabemos que las ventanas consecutivas se superponen significativamente, por lo que todo lo que necesitamos saber es la cantidad de elementos mayor que el elemento recién agregado y la cantidad de elementos menor que el elemento recién eliminado. Muchas veces, los algoritmos que realizan la misma o similares operaciones repetidamente pueden mejorarse mediante el uso de una estructura de datos más robusta. En nuestro caso, estamos buscando una estructura de datos dinámica que pueda responder de manera eficiente a las consultas sobre la posición relativa de un elemento cuando se ordena. Podemos usar un árbol binario autoequilibrado para mantener una lista ordenada, pero la inserción/eliminación lleva un tiempo logarítmico. Podemos hacer esto en tiempo constante usando un árbol indexado binario o árbol de Fenwick.
Un árbol indexado binario es un árbol representado en forma de array. Utiliza una manipulación inteligente de bits para calcular la suma acumulativa de elementos de manera muy eficiente. Podemos llamar a la función update(index, val) para agregar val a BIT[index] y todos los ancestros de index. La función read(index) devuelve la suma de los valores almacenados en BIT[index] y todos los ancestros de index en el árbol. Por lo tanto, llamar a read(index) devuelve la suma acumulada de todos los elementos en BIT menores o iguales que index . En lugar de almacenar valores, si simplemente almacenamos 1 , podemos usarread(index + 1) para determinar el número de elementos menos que index. Ahora, podemos construir un árbol indexado binario insertando los elementos (actualizando) de la primera ventana. Para ventanas posteriores, podemos eliminar el elemento final llamando a update(tail_element, -1) y agregar el nuevo elemento con update(head_element, 1) . Dado que se trata de un árbol, la ruta más larga posible del Node raíz es O(logk) . Por lo tanto, logramos un tiempo de ejecución óptimo de O(nlogk + klogk) = O(nlogk) .
¿O nosotros…? Recuerde, los árboles indexados binarios asignan memoria para cada valor posible en el rango [0, max_element] , por lo que esto requiere tiempo y espacio O(max_element) . Para arreglos muy dispersos, esto puede ser bastante costoso. En su lugar, podemos definir una función hash para . Podemos hacer esto porque solo nos preocupan las inversiones, siempre que mantengamos la magnitud relativa igual (es decir , A[i] <= A ==> A[hash(i)] <= A[hash(j) ] ), nuestra solución seguirá siendo correcta. Por lo tanto, podemos mapear todos los elementos en A al conjunto {0, 1, 2, …, n} , lo que genera un tiempo de ejecución garantizado de O(nlogk) .
Implementación:
Java
import java.util.*;
public class Subarray_Inversions {
// Declare binary indexed tree with global scope
static BIT bit;
// first window, counts first k elements and creates
// BIT
static long inversionCountBIT1(int[] arr, int start,
int end)
{
bit = new BIT(arr.length);
long count = 0;
for (int index = start; index >= end; index--) {
count += bit.read(arr[index]);
bit.update(arr[index], 1);
}
return count;
}
// subsequent windows, removes previous element, adds
// new element, and increments change in inversions
static long inversionCountBIT2(int[] arr, int start,
int end, long val)
{
bit.update(arr[start + 1], -1); // remove trailing element
// find number of elements in range [start, end-1]
// greater than first
int numGreaterThanFirst = start - end - bit.read(arr[start + 1] + 1);
long count = val + bit.read(arr[end]) - numGreaterThanFirst;
bit.update(arr[end], 1); // adds leading element
return count;
}
// Main method to count inversions in size k subarrays
public static long inversionCount(int n, int k, int[] arr)
{
bit = new BIT(n);
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
int[] asort = arr.clone();
// Map elements from [A[0]...A[n-1]] to [1...n]
Arrays.sort(asort);
int index = 0;
int current = 1;
for (int i = 0; i < n; i++) {
if (!freq.containsKey(asort[i])) {
freq.put(asort[i], current);
current++;
}
}
for (int i = 0; i < n; i++) {
arr[i] = freq.get(arr[i]);
}
long count = 0;
long val = 0;
//[start - end] ==> start - end = k+1
for (int start = n - 1; start >= k - 1; start--) {
int end = start - k + 1;
if (start == n - 1) { // First pass
val = inversionCountBIT1(arr, n - 1, n - k);
} else { // subsequent passes
val = inversionCountBIT2(arr, start, end, val);
}
count += val;
}
return count;
}
public static void main(String[] args) throws Exception
{
int n = 10;
int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
int k = 5;
long result = inversionCount(n, k, arr);
System.out.println(result);
}
// Implementation of Binary Indexed Tree
static class BIT {
int[] tree;
int maxVal;
public BIT(int N)
{
tree = new int[N + 1];
maxVal = N;
}
// Updates BIT, starting with element at index
// and all ancestors
void update(int index, int val)
{
while (index <= maxVal) {
tree[index] += val;
index += (index & -index);
}
}
// Returns the cumulative frequency of index
// starting with element at index and all ancestors
int read(int index)
{
--index;
int cumulative_sum = 0;
while (index > 0) {
cumulative_sum += tree[index];
index -= (index & -index);
}
return cumulative_sum;
}
};
}
C#
using System;
using System.Collections.Generic;
class Subarray_Inversions{
// Implementation of Binary Indexed Tree
public class BIT
{
public int[] tree;
public int maxVal;
public BIT(int N)
{
tree = new int[N + 1];
maxVal = N;
}
// Updates BIT, starting with element
// at index and all ancestors
public void update(int index, int val)
{
while (index <= maxVal)
{
tree[index] += val;
index += (index & -index);
}
}
// Returns the cumulative frequency
// of index starting with element at
// index and all ancestors
public int read(int index)
{
--index;
int cumulative_sum = 0;
while (index > 0)
{
cumulative_sum += tree[index];
index -= (index & -index);
}
return cumulative_sum;
}
};
// Declare binary indexed tree
// with global scope
static BIT bit;
// First window, counts first k elements
// and creates BIT
static long inversionCountBIT1(int[] arr, int start,
int end)
{
bit = new BIT(arr.Length);
long count = 0;
for(int index = start; index >= end; index--)
{
count += bit.read(arr[index]);
bit.update(arr[index], 1);
}
return count;
}
// Subsequent windows, removes previous element, adds
// new element, and increments change in inversions
static long inversionCountBIT2(int[] arr, int start,
int end, long val)
{
// Remove trailing element
bit.update(arr[start + 1], -1);
// Find number of elements in
// range [start, end-1] greater
// than first
int numGreaterThanFirst = start - end -
bit.read(arr[start + 1] + 1);
long count = val + bit.read(arr[end]) -
numGreaterThanFirst;
bit.update(arr[end], 1); // Adds leading element
return count;
}
// Main method to count inversions in size k subarrays
public static long inversionCount(int n, int k, int[] arr)
{
bit = new BIT(n);
Dictionary<int,
int> freq = new Dictionary<int,
int>();
int[] asort = (int[])arr.Clone();
// Map elements from [A[0]...A[n-1]] to [1...n]
Array.Sort(asort);
//int index = 0;
int current = 1;
for(int i = 0; i < n; i++)
{
if (!freq.ContainsKey(asort[i]))
{
freq.Add(asort[i], current);
current++;
}
}
for(int i = 0; i < n; i++)
{
arr[i] = freq[arr[i]];
}
long count = 0;
long val = 0;
//[start - end] ==> start - end = k+1
for(int start = n - 1; start >= k - 1; start--)
{
int end = start - k + 1;
if (start == n - 1)// First pass
{
val = inversionCountBIT1(arr, n - 1,
n - k);
}
else // subsequent passes
{
val = inversionCountBIT2(arr, start,
end, val);
}
count += val;
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int n = 10;
int[] arr = { 15, 51, 44, 44, 76,
50, 29, 88, 48, 50 };
int k = 5;
long result = inversionCount(n, k, arr);
Console.WriteLine(result);
}
}
// This code is contributed by Amit Katiyar
25
Este artículo es una contribución de Joel Abraham . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA