Java 中的情侣牵手问题

这是一个非常有趣的问题，经常在Google、Amazon、TCS、Accenture等顶级IT公司的面试中出现。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将用不同的方法和逻辑来解决Java中的情侣牵手问题。我们还将为此创建Java程序。

问题陈述

在这个问题中，我们有n对情侣，共2n人坐在2n个座位（排成一排），他们想要牵手。我们需要找到最少需要进行的交换（座位交换）次数，以便每对情侣都能坐在旁边。我们可以选择任意两个人进行交换，他们可以站起来并交换座位。

注意：数组的长度必须是偶数，否则会有一个人无法配对。

让我们通过示例来理解。

示例 1

输入： couple = [4, 1, 5, 2]

输出 1

解释： 在这里，我们只需要一次交换（1与5）就可以配对，我们得到 [4, 5, 1, 2]。在这里，人的顺序无关紧要。例如，[5, 4, 2, 1] 和 [4, 5, 1, 2] 是相同的。

示例 2

输入： couple = [1, 2, 8, 9]

输出 0

解释： 在这里，不需要交换座位，所有情侣已经手拉手了。

问题解决方案

为了解决这个问题，我们将定义一个整数数组 row。数组索引表示坐在第 i 个座位上的情侣。人和座位用0到2N-1的整数表示。情侣按顺序编号，第一对是(0, 1)，第二对是(2, 3)，以此类推，最后一对是(2N-2, 2N-1)。

这些情侣的初始座位 row[i] 由最初坐在第 i 个座位上的人决定。

这个问题可以用多种方法解决，例如使用并查集、贪心算法或排列图的循环分解。让我们逐一详细讨论。

解决方案1：使用排列图和图分解

排列图论允许给定一对排列，例如G1：(W, X, W, Y, W, Z, Y) 和 G2：(X, Y, Z, W, W, Y, W)。通过连接G1到G2的边，我们可以用图表示一对排列。根据观察，如果在任何位置[i]，我们有G1[i]=G2[i]，那么该顶点应该有一个自连接边。

为了将G2转换为G1，我们需要进行交换，以便移除两个顶点之间的边。简单来说，就是将顶点变成自连接边。

如果我们观察到图中的任何循环，移除所有非自连接边的最小步骤是边数-1。因此，总交换次数将是∑(C_k-1)，其中C₁, C₂, C₃, …. C_k是图中连通分量的长度。

我们还可以通过将图分解为不同的循环来最小化总交换次数，使每个循环尽可能小（因为边的数量是固定的，但我们得到的循环越多，交换次数就减去1的次数越多）。

步骤：

首先，确定图中连通部分的数量。为此，我们使用了一个名为 connectedNumber 的变量。

假设所有情侣都坐在一起，在这种情况下，连通部分的数量是row.length/2。

变量connectedNumber将在我们进行右交换以配对一对情侣时增加1。执行交换过程，直到变量connectedNumber等于row.length/2。所以这个问题的答案是row.length/2 - connectedNumber。

CoupleHoldingHands1.java

输出

1

解决方案2：贪心方法

如果我们仔细观察图（上面），会发现存在一个贪心的方法。只有一种方法可以将图分解，使得任何有助于匹配至少一对情侣的交换都是一个贪心操作。

在这个方法中，我们使用一个HashMap来计算每个人的位置。然后，再次遍历行。如果我们发现一对不匹配的人，我们就找到他们匹配的对象所在的位置并进行交换。我们持续执行贪心操作并计算交换次数。

CoupleHoldingHands2.java

输出

2

复杂度

以上所有方法的时空复杂度均为O(n)，其中n是情侣的数量。