Believe in science series, the analysis behind the two 100% solutions proved

This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 765 on LeetCode. Couples holding hands.

NNN Couples sit in a row of 2N2N2N seats, trying to hold hands with each other.

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 as integers from 000 to 2N− 12n-12n −1, and couples are numbered in order: the first pair is (0,1)(0, 1)(0,1), the second pair is (2,3)(2, 3)(2,3), and so on, The last pair is (2N−2,2N−1)(2n-2, 2n-1)(2N−2,2N−1).

The couples’ initial seat row[I]row[I]row[I] is determined by the person who initially sits in the third 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:

• Len (row) Len (row) is even and in the range of [4,60][4, 60][4,60].
• Row is guaranteed to be sequence 0… Len (row) – 10… len(row)-10… A full permutation of Len (row)−1.

Check and set

First of all, we always think in terms of “couples” :

1. When two couples sit on the wrong side of each other, a ring is formed between them. There needs to be an exchange to make each couple independent (hold hands with each other)

2. If three couples sit in the wrong place, they form a loop that needs to be switched twice, making each pair independent (holding hands with each other)

3. If four couples sit in the wrong position, they form a loop that needs to be switched three times to make each pair independent (holding hands with each other)

That is, if we have a KKK couple forming an error loop, it takes swapping k− 1K-1K −1 times to get the couple to hold hands.

So the question becomes
$n / 2$How many of these rings are there in a couple.

You can do this directly by using “look up sets”.

Due to the pairing of 0 and 1, 2 and 3… Therefore, the number of two couples divided by two corresponds to the same number, which can be directly used as their “couple group” number.

Code:

 class Solution {
    int[] p = new int[70];
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    int find(int x) {
        if(p[x] ! = x) p[x] = find(p[x]);return p[x];
    }
    public int minSwapsCouples(int[] row) {
        int n = row.length, m = n / 2;
        for (int i = 0; i < m; i++) p[i] = i;
        for (int i = 0; i < n; i += 2) {
            union(row[i] / 2, row[i + 1] / 2);
        }
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (i == find(i)) cnt++;
        }
        returnm - cnt; }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(n)O(n)O(n)

Greedy algorithm

Again, the analysis is carried out in the unit of “couples” :

Since they guarantee a solution, we can also work from the front to the back (every two squares as a step), for one position, if the next position is not the couple that should appear.

The next position is swapped.

In order to find the subscript of a value, we need to preprocess rowrowRow (hash table or array).

Code:

class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int ans = 0;
        int[] cache = new int[n];
        for (int i = 0; i < n; i++) cache[row[i]] = i;
        for (int i = 0; i < n - 1; i += 2) {
            int a = row[i], b = a ^ 1;
            if (row[i + 1] != b) {
                int src = i + 1, tar = cache[b]; cache[row[tar]] = src; cache[row[src]] = tar; swap(row, src, tar); ans++; }}return ans;
    }
    void swap(int[] nums, int a, int b) {
        intc = nums[a]; nums[a] = nums[b]; nums[b] = c; }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(n)O(n)O(n)

prove

What is the nature of what we are doing?

It’s essentially the same thing as when I get to number onekAt the time of the frontk - 1A couple in the same position has succeeded in holding hands. What do I do next to minimize the total cost.

There are two cases to discuss:

A. Now handle the KTH position and make it successfully hold hands:

Therefore, IF I want to make the couples in the KTH position also hold hands successfully, it must be one of the couples in the KTH position that is retained and then modified, which will cost the least (because it only needs to be exchanged once).

And since the couple in front has already succeeded in holding hands, the pair must be behind the k position.

And then we’re going to think about how swapping left or right affects the final result.

There are two cases to discuss:

1. With the firstkTwo couples in two positions are not in the same position: the number of couples that need to be adjusted is the same regardless of whether the left or right is switched. Hypothetical treatment controlkThe number of positions to be adjusted isnIf so, finish the firstkFor each position (switch left or right), the number of couples that need to be adjusted isn - 1 。

2. With the firstkTwo couples in the same position are matched in the same position: the number of couples that need to be adjusted is the same regardless of whether the left or the right is swapped. Hypothetical treatment controlkThe number of positions to be adjusted isnIf so, finish the firstkFor each position (switch left or right), the number of couples that need to be adjusted isn - 2 。

Therefore, for the KTH position, swapping left or right will not affect the “number of couples” that need to be adjusted later.

B. Do not deal with the KTH position now, and wait until the couple in the back deals with the KTH position “incidentally” :

Because we ultimately want couples in all positions to hold hands, and the number of couples corresponding to each value is uniquely determined.

So our “behind” position is actually equal to the position of the couple with the KTH position (corresponding to the figure above, we are waiting for [0 x] and [8 y] or [0 8] to be processed).

As all the connected positions are processed in the same batch, the analysis result is the same as that of “A. Now process the KTH position”.

Without loss of generality, we can extend this analysis to the first position, which in fact meets the definition of “by the time I get to the KTH position, the couples in the k-1 position in front of me are already holding hands.”

To sum up, we just need to make sure to process from front to back, and keep the n in each processkOne of the positions, either the left or the right, will get the optimal solution.

The last

This is the No.765 article in our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.