Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

765. Lovers hold hands

N couples are sitting in 2N consecutive seats, trying to hold each other’s hands. Count the minimum number of times you can switch seats so that each couple can sit side by side. Choose any two people at a time and have them stand up and switch seats.

People and seats are represented by integers from 0 to 2n-1, and couples are numbered in order, with the first pair (0, 1), the second pair (2, 3), and so on, and the last pair (2N-2, 2N-1).

The couples’ initial seat row[I] is determined by the person who originally sat in the ith seat.

Example 1:

Input: row = [0, 2, 1, 3] Output: 1 Explanation: We simply swap the positions of row[1] and row[2].Copy the code

Example 2:

Input: row = [3, 2, 0, 1] Output: 0 Explanation: All couples can already hold hands without switching seats.Copy the code

Description:

  1. len(row)Is even and the value is in[4, 60]Within the scope.
  2. Can guaranteerowIs a sequence0... len(row)-1A complete permutation of.

Train of thought

  1. The realization of this problem is very simple, difficult is the transformation of thinking. Like Ben1and2.3and4I’m supposed to hold hands, but this seat is1and3.2and4We all know at a glance that we can just switch places once. But how do you let elements in the code world know about this?
  2. We can establish1and3.2and4The link relationship of. We’ll find that as soon as1and2Holding hands, so3and4Of course, he also held hands;
  3. This scenario is called parallel search set in our algorithm time, we first go through a round, establish the initialization of the link between the two;
  4. Then through the second round of traversal, the two adjacent to the line, if they signed the line, there are two other people through them to connect, so that the two after a round of seat exchange can just meet the purpose of both sides to hold hands;
  5. You can return directly after counting our matchmaking times.

implementation

/ * * *@param {number[]} row
 * @return {number}* /
var minSwapsCouples = function(row) {
    const n = row.length;
    const uf = new UnionFind(n);

    const mid = n / 2;
    // Connect the current value first
    for (let i = 0; i < mid; i++) {
        uf.merge(row[2 * i], row[2 * i + 1]);
    }

    let count = 0;
    // Let's see how many unconnected ones are strung together
    for (let i = 0; i < mid; i++) {
        let index1 = uf.find(2 * i), index2 = uf.find(2 * i + 1);

        // If adjacent positions are not connected, string them together
        if (index1 !== index2) {
            uf.merge(index1, index2);
            count++;
        }
    }

    return count;
};

class UnionFind {
  constructor(n) {
    // The parent of each element is itself
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find the parent of the element
  find(index) {
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Set the parent of index2 to the parent of index1
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.