Dada una array , arr[] de tamaño N que denota una permutación de números de 1 a N , la tarea es contar el número de inversiones en la array .
Nota: dos elementos de array a[i] y a[j] forman una inversión si a[i] > a[j] e i < j.
Ejemplos:
Entrada: arr[] = {2, 3, 1, 5, 4}
Salida: 3
Explicación: La array dada tiene 3 inversiones: (2, 1), (3, 1) , (5, 4).Entrada: arr[] = {3, 1, 2}
Salida: 2
Explicación: La array dada tiene 2 inversiones: (3, 1), (3, 2).
Se han discutido diferentes métodos para resolver el conteo de inversión en los siguientes artículos:
Enfoque: este problema se puede resolver utilizando la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Almacene los números en el rango [1, N] en orden creciente en un vector, V .
- Inicializa una variable, ans como 0 para almacenar el número de inversiones en la array, arr[] .
- Iterar en el rango [0, N-1] usando la variable i
- Almacene el índice de aparición de arr[i] en el vector V en una variable index .
- Agregue el recuento de números que tienen posiciones menores que el índice que están presentes en el vector, V , ya que son más pequeños que el elemento actual y, por lo tanto, forman inversiones.
- Retire el elemento en el índice de posición del vector , V .
- Imprime el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count number of inversions in
// a permutation of first N natural numbers
int countInversions(int arr[], int n)
{
vector<int> v;
// Store array elements in sorted order
for (int i = 1; i <= n; i++) {
v.push_back(i);
}
// Store the count of inversions
int ans = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Store the index of first
// occurrence of arr[i] in vector V
auto itr = lower_bound(
v.begin(), v.end(), arr[i]);
// Add count of smaller elements
// than current element
ans += itr - v.begin();
// Erase current element from
// vector and go to next index
v.erase(itr);
}
// Print the result
cout << ans;
return 0;
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 2, 3, 1, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
countInversions(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.util.Vector;
class GFG{
// Function to count number of inversions in
// a permutation of first N natural numbers
static void countInversions(int arr[], int n)
{
Vector<Integer> v = new Vector<>();
// Store array elements in sorted order
for(int i = 1; i <= n; i++)
{
v.add(i);
}
// Store the count of inversions
int ans = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// Store the index of first
// occurrence of arr[i] in vector V
int itr = v.indexOf(arr[i]);
// Add count of smaller elements
// than current element
ans += itr;
// Erase current element from
// vector and go to next index
v.remove(itr);
}
// Print the result
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
// Given Input
int arr[] = { 2, 3, 1, 5, 4 };
int n = arr.length;
// Function Call
countInversions(arr, n);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach from bisect import bisect_left # Function to count number of inversions in # a permutation of first N natural numbers def countInversions(arr, n): v = [] # Store array elements in sorted order for i in range(1, n + 1, 1): v.append(i) # Store the count of inversions ans = 0 # Traverse the array for i in range(n): # Store the index of first # occurrence of arr[i] in vector V itr = bisect_left(v, arr[i]) # Add count of smaller elements # than current element ans += itr # Erase current element from # vector and go to next index v = v[:itr] + v[itr + 1 :] # Print the result print(ans) # Driver Code if __name__ == '__main__': # Given Input arr = [ 2, 3, 1, 5, 4 ] n = len(arr) # Function Call countInversions(arr, n) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count number of inversions in
// a permutation of first N natural numbers
static void countInversions(int[] arr, int n)
{
List<int> v = new List<int>();
// Store array elements in sorted order
for (int i = 1; i <= n; i++) {
v.Add(i);
}
// Store the count of inversions
int ans = 0;
// Traverse the array
for(int i =0 ;i <n;i ++){
// Store the index of first
// occurrence of arr[i] in vector V
int itr = v.IndexOf(arr[i]);
// Add count of smaller elements
// than current element
ans += itr;
// Erase current element from
// vector and go to next index
v.RemoveAt(itr);
}
// Print the result
Console.WriteLine(ans);
}
// Driver code
public static void Main(string[] args)
{
// Given Input
int[] arr = { 2, 3, 1, 5, 4 };
int n = arr.Length;
// Function Call
countInversions(arr, n);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to count number of inversions in
// a permutation of first N natural numbers
function countInversions(arr, n)
{
var v = [];
var i;
// Store array elements in sorted order
for(i = 1; i <= n; i++)
{
v.push(i);
}
// Store the count of inversions
var ans = 0;
// Traverse the array
for(i = 0; i < n; i++)
{
// Store the index of first
// occurrence of arr[i] in vector V
var index = v.indexOf(arr[i]);
// Add count of smaller elements
// than current element
ans += index;
// Erase current element from
// vector and go to next index
v.splice(index, 1);
}
// Print the result
document.write(ans);
}
// Driver code
// Given Input
var arr = [ 2, 3, 1, 5, 4 ];
var n = arr.length;
// Function Call
countInversions(arr, n);
// This code is contributed by bgangwar59
</script>
Producción:
3
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por adarsh_sinhg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA