Блог пользователя wish_me

Автор wish_me, история, 6 лет назад, По-английски

There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n. All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other.

n<10^3 arr.size<10^3

Input: n = 3

pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on

arr[] = {3, 5, 6, 4, 1, 2}

Output: 2

We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1

(Google Interview)

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    your jokes are worth your rating

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That wasn't a joke... I was just telling him to first google the question and then only ask here.

      PS-> Your views tell a lot about your thinking about people below you(rating wise)... God bless you :-)

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Let's call a spade a spade. That wasn't a friendly advice to google the question. He is wise who says nothing when he has nothing to say.

        PS-> Your jokes tell a lot about your thinking about people below you(rating wise)... God bless you :-)

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Up. I met this problem before and know linear reference solution but I can't prove it :(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The solution which makes swaps along the cycles of permutation?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Yep.

      Consider first two elements. If they are partners then skip them and move to the next two elements. Otherwise find a pair for any of these two elements (suppose the pair was among a[2k] and a[2k + 1]), make swap, now move to elements with indexes 2k and 2k + 1 and repeat step.