Minimum number of swaps

Правка en1, от altruist, 2017-07-03 16:05:02

Hello everybody. Recently, I was thinking about a one problem and now I want to share it with you:

You have two arrays of the same length n, and you have to calculate minimum number of swaps of two arbitrary indexes which transform the first array A into the second B. ( All elements in arrays are not neccessery distinct ) I know how to solve this problem when all elements are distinct in O(n). Do you know how to solve common problem in effective asymptotics?

Thank you in advance!

Теги permutations, minimum number of swaps

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский altruist 2017-07-03 16:05:02 518 Initial revision for English translation
ru1 Русский altruist 2017-07-02 16:01:52 719 Первая редакция (опубликовано)