2023-04-14:n对情侣坐在连续排列的 2n 个座位上,想要牵到对方的手, 人和座位由一个整数数组 row 表示,其中 row[i] 是坐在第 i 个座位
数组 一个 2023 表示 14 整数 连续 04
2023-06-13 09:18:33 时间
2023-04-14:n对情侣坐在连续排列的 2n 个座位上,想要牵到对方的手,
人和座位由一个整数数组 row 表示,其中 rowi 是坐在第 i 个座位上的人的ID,
情侣们按顺序编号,第一对是 (0, 1),第二对是 (2, 3),以此类推,最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数,以便每对情侣可以并肩坐在一起。
每次交换可选择任意两人,让他们站起来交换座位。
输入: row = 0,2,1,3。
输出: 1。
输入: row = 3,2,0,1。
输出: 0。
答案2023-04-14:
大体过程如下:
- 定义并查集结构体 UnionFind,包括父节点数组 father、子树大小数组 size、辅助数组 help 和当前连通分量数 sets。
- 实现并查集结构体的三个方法:
a. 初始化方法 new,初始化父节点数组和子树大小数组,并将父节点数组的值初始化为自身,连通分量数初始为节点数量。
b. 查找方法 find,通过不断向上寻找父节点,直到找到根节点,并压缩路径优化查找效率。
c. 合并方法 union,找到 i 和 j 所在的连通分量的代表元素 fi 和 fj,以子树大小来优化合并操作,并更新连通分量数。
- 实现计算最少交换座位次数的函数 min_swaps_couples,首先获取座位数量 n,然后初始化并查集 uf,遍历相邻的座位,将情侣所在的连通分量合并。最后返回需要交换座位的最小次数。
- 在 main 函数中分别调用 min_swaps_couples 函数,传入测试数据,并输出最少交换座位的次数。
- 根据测试数据 row = 0, 2, 1, 3,第一对情侣坐在座位0和1上,第二对情侣坐在座位2和3上,因此已经满足牵手的条件。而在测试数据 row = 3, 2, 0, 1 中,第一对情侣坐在座位3和2上,第二对情侣坐在座位0和1上,因此需要交换他们的座位才能满足牵手的条件。
并查集的初始化时间复杂度为O(n),其中n为节点数量。在计算最少交换座位次数的函数 min_swaps_couples 中,遍历相邻的座位需要O(n) 的时间,每次调用并查集中的 find 方法和 union 方法的时间复杂度均为O(α(n)),其中α(n) 是阿克曼函数的反函数,它比对数函数增长得慢,可以近似看作常数级别。因此,总时间复杂度为O(nα(n))。
空间复杂度取决于节点数量,需要使用O(n) 的空间存储父节点数组、子树大小数组和辅助数组。
rust代码如下:
// 定义并查集结构体
struct UnionFind {
father: Vec<i32>, // 父节点数组
size: Vec<i32>, // 子树大小数组
help: Vec<i32>, // 辅助数组,用于优化路径压缩操作
sets: i32, // 当前连通分量数
}
impl UnionFind {
// 初始化并查集
fn new(n: i32) -> Self {
let mut father = vec![0; n as usize]; // 初始化父节点数组
let size = vec![1; n as usize]; // 初始化子树大小数组
for i in 0..n {
father[i as usize] = i; // 父节点初始化为自身
}
UnionFind {
father, // 返回新建的并查集结构体
size,
help: vec![0; n as usize],
sets: n, // 初始时连通分量数为n
}
}
// 查找i所在连通分量的代表元素
fn find(&mut self, mut i: i32) -> i32 {
let mut hi = 0;
while i != self.father[i as usize] {
// 不断向上寻找父节点,直到找到根节点
self.help[hi] = i; // 将当前节点压入辅助数组中
hi += 1;
i = self.father[i as usize]; // 向上跳一步
}
for j in (0..hi).rev() {
// 压缩路径
self.father[self.help[j] as usize] = i; // 将辅助数组中的节点的父节点设为根节点
}
i // 返回根节点
}
// 合并i和j所在的连通分量
fn union(&mut self, i: i32, j: i32) {
let fi = self.find(i); // 找到i的代表元素
let fj = self.find(j); // 找到j的代表元素
if fi != fj {
// 如果i和j不在同一个连通分量中
if self.size[fi as usize] >= self.size[fj as usize] {
// 以树的大小来优化合并操作
self.father[fj as usize] = fi; // 将fj的父节点设为fi
self.size[fi as usize] += self.size[fj as usize]; // 更新fi子树的大小
} else {
self.father[fi as usize] = fj; // 将fi的父节点设为fj
self.size[fj as usize] += self.size[fi as usize]; // 更新fj子树的大小
}
self.sets -= 1; // 连通分量数减1
}
}
// 获取当前连通分量数
fn sets(&self) -> i32 {
self.sets
}
}
// 计算最少交换座位的次数
fn min_swaps_couples(row: Vec<i32>) -> i32 {
let n = row.len() as i32; // 座位数量
let mut uf = UnionFind::new(n / 2); // 初始化并查集
for i in (0..n).step_by(2) {
// 遍历相邻的座位
uf.union(row[i as usize] / 2, row[(i + 1) as usize] / 2); // 合并情侣所在的连通分量
}
n / 2 - uf.sets() // 返回需要交换座位的最小次数
}
fn main() {
let row = vec![0, 2, 1, 3];
let swaps = min_swaps_couples(row);
println!("Minimum swaps required: {}", swaps); // Output: Minimum swaps required: 1
let row = vec![3, 2, 0, 1];
let swaps = min_swaps_couples(row);
println!("Minimum swaps required: {}", swaps); // Output: Minimum swaps required: 0
}
相关文章
- js 实现扁平数组转为树形结构数组及树形结构数组转为扁平数组
- java 输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组
- 【说站】python有哪些数组叠加函数
- 2022-10-21:你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。 你要用 所有的火柴棍 拼成
- 「后端小伙伴来学前端了」Vue中 this.$set的用法 | 可用于修改对象中数组的某一个对象、 可用于更新数据到视图
- js数组删除某一个元素_删除数组中重复元素
- 2022-12-26:有一个数组包含0、1、2三种值, 有m次修改机会,第一种将所有连通的1变为0,修改次数-1, 第二种将所有连通的2变为1或0,修改次数-2
- 2023-01-14:给定一个二维数组map,代表一个餐厅,其中只有0、1两种值 map[i][j] == 0 表示(i,j)位置是空座 map[i][j] =
- 2022-11-04:给定一个正数n,表示有多少个节点给定一个二维数组edges,表示所有无向边edges[i] = {a, b
- 2023-02-16:两种颜色的球,蓝色和红色,都按1~n编号,共计2n个, 为方便放在一个数组中,红球编号取负,篮球不变,并打乱顺序, 要求同一种颜色的球按编
- 【算法】js求一个数组的幂集
- 2023-04-19:给定一个非负数组arr 任何两个数差值的绝对值,如果arr中没有,都要加入到arr里 然后新的arr继续,任何两个数差值的绝对值,如果ar
- java数组转换为List注意地方详解编程语言
- js数组去重详解编程语言
- 掌握 Oracle 数组使用技巧(oracle数组使用)
- C语言实现MySQL数组插入技巧(c mysql插入数组)
- Oracle中使用字符串数组的最佳方式(oracle中字符串数组)
- SortingArrayValuesinPHP(数组排序)
- php数组函数序列之ksort()对数组的元素键名进行升序排序,保持索引关系
- Javascript中克隆一个数组的实现代码
- $.each遍历对象、数组的属性值并进行处理
- Python数组条件过滤filter函数使用示例