情侣牵手
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.2 MB
/*
题目思路：
使用Java Stream的API来进行类似操作。尽管不是很符合功能式编程风格，
但我们依然可以通过流式操作来简化一些代码。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Solution {
public int minSwapsCouples(int[] row) {
int n = row.length;
int[] pos = IntStream.range(0, n).map(i -> row[i]).toArray();
IntStream.range(0, n).forEach(i -> pos[row[i]] = i);
return IntStream.range(0, n / 2).map(i -> {
int first = row[2 * i];
int second = first ^ 1;
if (row[2 * i + 1] == second) return 0;
int swapIdx = pos[second];
pos[row[2 * i + 1]] = swapIdx;
row[swapIdx] = row[2 * i + 1];
pos[second] = 2 * i + 1;
row[2 * i + 1] = second;
return 1;
}).sum();
}
}解释
方法:
此题解采用了并查集的数据结构来解决情侣牵手的问题。首先创建一个UnionSet类来处理并查集相关的操作，包括初始化、查找和合并。题目中的每对情侣编号为(0,1), (2,3)等，意味着两个人的ID除以2的结果如果相同，则它们是一对。算法的核心在于将每对坐在一起的情侣通过union操作合并在同一个集合中。每次合并减少一个集合，初始集合数为n对情侣即n/2。最后，需要的交换次数为初始集合数减去最后的集合数，即n/2 - uset.set。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在并查集中，为什么需要使用路径压缩技术？这对算法的性能有什么具体影响？
▷🦆
并查集的`union`操作中，为何选择按秩合并？这样做的好处是什么？
▷🦆
题解中提到对每对情侣执行`uset.union(row[i]//2, row[i+1]//2)`操作，这里除以2的意图是什么？为什么这样可以正确地识别情侣对？
▷🦆
在实际的并查集实现中，`self.size[fy] = None`和`self.size[fx] = None`的操作是否有误？应该如何正确处理？
▷相关问题
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都 独一无二
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
相似度为 K 的字符串
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
示例 1：
输入：s1 = "ab", s2 = "ba" 输出：1
示例 2：
输入：s1 = "abc", s2 = "bca" 输出：2
提示：
1 <= s1.length <= 20s2.length == s1.lengths1和s2只包含集合{'a', 'b', 'c', 'd', 'e', 'f'}中的小写字母s2是s1的一个字母异位词