Полезно заметить, что если использовать для разбиения на компоненты связности подход с Disjoint Set Unions
, — можно получить решение, работающее на практике в 2 раза быстрее за счёт более эффективных аллокаций памяти (нет необходимости поддерживать списки смежности).
struct UnionFind {
parent: Vec<usize>,
size: Vec<usize>,
min_and: Vec<i32>,
}
impl Solution {
pub fn minimum_cost(n: i32, edges: Vec<Vec<i32>>, query: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let mut uf = UnionFind::new(n);
// Process edges to construct the Union-Find structure
for edge in &edges {
let (u, v, w) = (edge[0] as usize, edge[1] as usize, edge[2]);
uf.union(u, v, w);
}
// Process queries efficiently
query.into_iter().map(|q| {
let (s, t) = (uf.find(q[0] as usize), uf.find(q[1] as usize));
if s == t { uf.min_and[s] } else { -1 }
}).collect()
}
}
impl UnionFind {
fn new(n: usize) -> Self {
UnionFind {
parent: (0..n).collect(),
size: vec![1; n],
min_and: vec![-1; n],
}
}
fn find(&mut self, x: usize) -> usize {
if self.parent[x] != x {
self.parent[x] = self.find(self.parent[x]); // Path compression
}
self.parent[x]
}
fn union(&mut self, a: usize, b: usize, weight: i32) {
let mut root_a = self.find(a);
let mut root_b = self.find(b);
if root_a != root_b {
// Union by size: attach the smaller tree under the larger tree
if self.size[root_a] < self.size[root_b] {
std::mem::swap(&mut root_a, &mut root_b);
}
self.parent[root_b] = root_a;
self.size[root_a] += self.size[root_b];
self.min_and[root_a] &= self.min_and[root_b];
}
// Update min_and for the new root
self.min_and[root_a] &= weight;
}
}
перейти
Привычное итеративное решение, конечно, стоит также привести для сравнения
impl Solution {
pub fn longest_nice_subarray(nums: Vec<i32>) -> i32 {
let mut current_bitset = 0;
let mut max_len = 0;
let mut left = 0;
for (right, &val) in nums.iter().enumerate() {
// Shrink the window if nums[right] conflicts with current_bitset
while current_bitset & val != 0 {
current_bitset ^= nums[left];
left += 1;
}
// Expand the window by including nums[right]
current_bitset |= val;
max_len = max_len.max((right - left + 1) as i32);
}
max_len
}
}
перейти
Стоит также обратить внимание на чуть более медленное, зато короткое решение через стабильную сортировку
impl Solution {
pub fn pivot_array(mut nums: Vec<i32>, pivot: i32) -> Vec<i32> {
nums.sort_by_key(|&num| num.cmp(&pivot)); nums
}
}
перейти