Pregunta De la Entrevista: Reverse pares

Question

Tengo esto para mi entrevista:

números se dice que están "marcha atrás ordenada" si N [i]> N [j] para i < j. Por ejemplo, en una lista: 3 4 1 6 7 3, los artículos ordenados en reversa son (3,1) (4,1) (4,3) (6,3) (7,3).

Cómo obtener el número de pares de elementos ordenados en reversa en el tiempo O (nlogn).

Answer 1

Es posible hacer esto en el tiempo O (n log n) usando una versión modificada del tipo de fusión. Haz la división como siempre, pero puedes contar las inversiones a medida que te fusionas. Cada vez que seleccione un elemento de la lista de la derecha sobre un elemento de la lista de la izquierda, incremente el recuento de inversiones por el número de elementos restantes en la lista de la izquierda. Entonces, en cada nivel, el número de inversiones es el número de inversiones encontradas durante la combinación más las inversiones encontradas por cada llamada recursiva.

Answer 2

Nota, lea la parte inferior de esta respuesta para ver por qué es realmente posible hacer el problema. Leí la pregunta mal.

No es posible en el caso general. Considere la lista:

n, n-1, n-2 ... 4, 3, 2, 1

Los pares serán:

(n, n-1), (n , n-2) ... (n, 2), (n, 1), (n-1, n-2), (n-1, n-3) ... ... (3, 2) , (3, 1), (2, 1)

por lo tanto hay O (n^2) pares y por lo tanto la lista no se puede construir en O (n log n)

sin embargo, se puede hacer esto con un pase de la lista:

1. comenzar al final de la lista y trabajar con las contraseñas.
2. mientras se desplaza por la lista mantenga un montón de los números que ha visto (esto hará que el bucle sea O (n log n))
3. por cada número que encuentre haga una búsqueda en el montón para encontrar todos los números que son menos que el número en el que se encuentra actualmente. Muestra el número actual y el número en el montón como un par. (Esto es O (n log n) para encontrar el primer partido en el montón, pero será O (n) para encontrar todos los números más pequeños)

Para su ejemplo:

La lista: 3 4 1 6 7 3

comenzando en el segundo elemento

montón (3) artículo (7)

de salida (7, 3)

montón (3, 7) elemento (6)

búsqueda y encontrar los 7, la salida (6, 3)

montón (3, 6, 7) elemento (1)

buscar y encontrar nada

montón (1, 3, 6, 7) material (4)

búsqueda y encontrar los 3 y 1. salida (4, 3) (4, 1)

etc ....

Edición, es posible realidad

Desde JoshD observó correctamente que estamos buscando el número de elementos, se puede utilizar un árbol B en lugar de un montón y entonces se puede obtener sólo la cuenta de elementos menos que el elemento actual y agregarlo a un contador.

Answer 3

Esto se puede resolver creando un árbol de búsqueda binaria de modo que cada nodo contenga el tamaño de su subárbol izquierdo.

Los valores se agregan a la BST en orden inverso al de la matriz original. Se guarda una suma y cada vez que vamos a la derecha cuando agregamos un nodo, el nodo actual que se compara con el subárbol izquierdo + 1 se suma a la suma final (dado que el valor agregado es mayor que ese nodo y cada valor en su izquierda subárbol).

La construcción del árbol es nlogn y una vez que se construye el árbol, la suma será el número de pares.

necesidades de manipulación de especialmente para ser añadido para los números duplicados en función de las necesidades (es decir, si (4,3) muestra dos veces, en caso de ser contados dos veces)

Answer 4

de derecha a izquierda de recorrido, árbol Rojo-Negro donde cada nodo se aumenta por el tamaño de su subárbol respectivo. Entonces, toma O (logn) para encontrar la cantidad de elementos debajo de uno dado.

Answer 5

Como señala @ jlewis42, puede usar una versión modificada del tipo de fusión. Solo quería agregar que puede usar cualquiera de los algoritmos estándar comparison sort, siempre y cuando el peor tiempo de ejecución sea n log n, al "instrumentarlo" para contar las inversiones a medida que funciona. Ver también this cerca de dupe.