Как найти пары обратного порядка в двух массивах?

Question

Это вопрос для интервью .Есть два массива A1 и A2.Найдите пары чисел в A2, которые были в обратном порядке в A1.Например, A1 = [2 6 5 8 1 3], A2 = [1 2 3 4 5 6].Ответ: (1, 2), (1, 5), (1, 6), (5, 6), (3, 5), (3, 6).

O (N ^ 2) алгоритм тривиален.Есть ли лучший алгоритм?Что ты думаешь?

Answer 1

Если у вас есть шаблон, такой как A1 = 1111122222 и A2 = 2222211111, то вы получите (N / 2) ⁴ пар. Поэтому в худшем случае вы не можете сделать лучше, чем O (N ⁴ ).

Ниже приведено решение O (N ⁴ ), которое обрабатывает дубликаты и некоторые числа, встречающиеся только в одном из двух списков. Обратите внимание, что хотя в худшем случае это O (N ⁴ ), его средний случай O (N ² ) гораздо более вероятен, аналогично сложности быстрой сортировки . * * 1015

index = {} # dictionary of lists defaulting to []
for i in 0..len(A2):
  index[A2[i]].append(i)
for i1 in 0..len(A1):
  for j1 in i+1..len(A1):
    for i2 in index[A1[i1]]:
      for j2 in index[A1[j1]]:
        if i2 != j2 and i1 < j1 != i2 < j2:
          print A1[i1], A1[j1]

Если мы слегка ослабим формат вывода, чтобы разрешить вывод (1, 2) * 7, чтобы указать 7 разворотов, то мы можем добиться большего. Сначала заархивируйте списки, указав [(2, 1), (6, 2), (5, 3), (8, 4), (1, 5), (3, 6)] для примера. Сортируйте массивы с помощью стабильной сортировки: сначала используйте первый элемент в каждом кортеже, затем сортируйте другую копию списка, используя второй элемент в кортеже. Затем используйте адаптированную сортировку слиянием, подобную упомянутой здесь , но вместо того, чтобы считать, мы производим, мы выводим инверсии. Это решение O (NlogN).

Answer 2

Если оба массива имеют одинаковые элементы, и A1 - это перестановка A2 (которая отсортирована), мы можем изменить сортировку слиянием, чтобы подсчитать количество инверсий, присутствующих в A1.

http://geeksforgeeks.org/?p=3968

Answer 3

Я думаю, что этот алгоритм довольно близок к лучшему.Если мы отбросим вычислительную стоимость построения дерева (n ^ 2), у нас останется стоимость n (n-1) / 2 операций.Он как-то использует три, чтобы сделать константу проверки стоимости пары постоянной.При необходимости вы можете, за счет len (a) + len (b), отсканировать два массива и сделать вывод, что такое MAX:

#include "stdio.h"
#include "stdlib.h"

#define MAX 9
#define AEL 6
#define BEL 6

int main(){
    int b[BEL] = {2,6,5,8,1,3};
    int a[AEL] = {1,2,3,4,5,6};
    int **trie = calloc(MAX,sizeof(int*));
    int i,j;

    for(i = 0; i < MAX; i++){
        trie[i] = calloc(MAX,sizeof(int));
    }

    for(i = 0; i < AEL; i++){
        for(j = i+1; j < AEL; j++){
            trie[a[i]][a[j]] = 1;
        }
    }

    for(i = 0; i < BEL; i++ ){
        for(j = i+1; j < BEL ; j++){
            if(trie[b[j]][b[i]]){
                printf("(%d %d) ",b[j],b[i]);
            }
        }
    }

    return 0;
}