Encuentre la diferencia de compatibilidad entre dos arreglos

Supongamos que hay dos amigos y ahora quieren probar su amistad para ver qué tan compatibles son. Dados los números n numerados de 1…n y se les pide que ordenen los números. La tarea es encontrar la diferencia de compatibilidad entre ellos. La diferencia de compatibilidad es el número de desajustes en la clasificación relativa de la misma película dada por ellos.

Ejemplos:  

Input : a1[] = {3, 1, 2, 4, 5} 
        a2[] = {3, 2, 4, 1, 5}
Output : 2
Explanation : Compatibility difference is two
because first ranks movie 1 before 2 and 4 but
other ranks it after.

Input : a1[] = {5, 3, 1, 2, 4} 
        a2[] = {3, 1, 2, 4, 5}
Output : 5
Total difference is four due to mis-match in
position of 5

Preguntado en Walmart Labs 

La idea es atravesar ambas arrays. 

1. Si los elementos actuales son los mismos, no haga nada. 
2. Encuentre la siguiente posición de a1[i] en a2[]. Sea esta posición j. Uno por uno, mueva a2[j] a a2[i] (similar al paso de burbuja del tipo de burbuja )

A continuación se muestra la implementación de los pasos anteriores. 

// C++ program to count of misplacements
#include <bits/stdc++.h>
using namespace std;
int findDifference(int a1[], int a2[], int n)
{
    int res = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If elements at current position
        // are not same
        if (a1[i] != a2[i]) {
 
            // Find position of a1[i] in a2[]
            int j = i + 1;
            while (a1[i] != a2[j])
                j++;
             
            // Insert the element a2[j] at
            // a2[i] by moving all intermediate
            // elements one position ahead.
            while (j != i) {
                swap(a2[j], a2[j - 1]);
                j--;
                res++;
            }
        }
    }
    return res;
}
 
// Driver code
int main()
{
    int a1[] = { 3, 1, 2, 4, 5 };
    int a2[] = { 3, 2, 4, 1, 5 };
    int n = sizeof(a1)/sizeof(a1[0]);
    cout << findDifference(a1, a2, n);
    return 0;
}

// Java program to count of misplacements
public class Compatability_difference {
 
    static int findDifference(int a1[], int a2[], int n)
    {
        int res = 0;
      
        for (int i = 0; i < n; i++) {
      
            // If elements at current position
            // are not same
            if (a1[i] != a2[i]) {
      
                // Find position of a1[i] in a2[]
                int j = i + 1;
                while (a1[i] != a2[j])
                    j++;
                  
                // Insert the element a2[j] at
                // a2[i] by moving all intermediate
                // elements one position ahead.
                while (j != i) {
                     
                    //swap
                    int temp = a2[j - 1];
                    a2[j - 1] = a2[j];
                    a2[j] = temp;
                    j--;
                    res++;
                }
            }
        }
        return res;
    }
      
    // Driver code
    public static void main(String args[])
    {
        int a1[] = { 3, 1, 2, 4, 5 };
        int a2[] = { 3, 2, 4, 1, 5 };
        int n = a1.length;
         
        System.out.println(findDifference(a1, a2, n));
    }
}
// This code is contributed by Sumit Ghosh

# Python3 program to count misplacements
 
def findDifference(a1, a2, n):
 
    res = 0
 
    for i in range(0, n):
 
        # If elements at current
        # position are not same
        if a1[i] != a2[i]:
 
            # Find position of a1[i] in a2[]
            j = i + 1
            while (a1[i] != a2[j]):
                j += 1
                if i >= n or j >= n:
                    break
             
            # Insert the element a2[j] at
            # a2[i] by moving all intermediate
            # elements one position ahead.
            while (j != i):
                a2[j],a2[j-1] = a2[j-1],a2[j]
                res += 1
                j -= 1
                if i >= n or j >= n:
                    break
         
    return res
 
# Driver code
a1 = [ 3, 1, 2, 4, 5 ]
a2 = [ 3, 2, 4, 1, 5 ]
n = len(a1)
print(findDifference(a1, a2, n))
 
# This code is contributed by Smitha Dinesh Semwal

// C# program to count of misplacements
using System;
 
public class Compatability_difference
{
    static int findDifference(int []a1, int []a2, int n)
    {
        int res = 0;
     
        for (int i = 0; i < n; i++) {
     
            // If elements at current
            // position are not same
            if (a1[i] != a2[i]) {
     
                // Find position of a1[i] in a2[]
                int j = i + 1;
                while (a1[i] != a2[j])
                    j++;
                 
                // Insert the element a2[j] at
                // a2[i] by moving all intermediate
                // elements one position ahead.
                while (j != i) {
                     
                    //swap
                    int temp = a2[j - 1];
                    a2[j - 1] = a2[j];
                    a2[j] = temp;
                    j--;
                    res++;
                }
            }
        }
        return res;
    }
     
    // Driver code
    public static void Main()
    {
        int []a1 = {3, 1, 2, 4, 5};
        int []a2 = {3, 2, 4, 1, 5};
        int n = a1.Length;
         
        // Function calling
        Console.WriteLine(findDifference(a1, a2, n));
    }
}
 
// This code is contributed by vt_m.

<script>
 
// JavaScript program to count of misplacements
function findDifference(a1, a2, n)
{
    let res = 0;
 
    for(let i = 0; i < n; i++)
    {
         
        // If elements at current position
        // are not same
        if (a1[i] != a2[i])
        {
             
            // Find position of a1[i] in a2[]
            let j = i + 1;
            while (a1[i] != a2[j])
                j++;
             
            // Insert the element a2[j] at
            // a2[i] by moving all intermediate
            // elements one position ahead.
            while (j != i)
            {
                 
                // Swap
                let temp = a2[j - 1];
                a2[j - 1] = a2[j];
                a2[j] = temp;
                j--;
                res++;
            }
        }
    }
    return res;
}
 
// Driver code
let a1 = [ 3, 1, 2, 4, 5 ];
let a2 = [ 3, 2, 4, 1, 5 ];
let n = a1.length;
 
document.write(findDifference(a1, a2, n));
    
// This code is contributed by sravan kumar
 
</script>

2

Este artículo es una contribución de Rakesh Kumar . 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.