Задача на сегодня 2657. Find the Prefix Common Array of Two Arrays решается в лоб, но иногда стоит рассматривать и такие простые!
📝 Описание задачи
Даны две перестановки целых чисел A и B длины n. Необходимо вычислить массив общего префикса C, где C[i] равен количеству чисел, присутствующих в обеих перестановках на индексах от 0 до i.
Пример:
- Input:
A = [1,3,2,4], B = [3,1,2,4]
- Output:
[0,2,3,4]
💡 Идея
Чтобы быстро подсчитать количество общих элементов в префиксе, мы будем использовать два булевых массива для отслеживания того, какие элементы уже встречались в каждой из перестановок. Это позволит эффективно определять, какие элементы являются общими на каждом шаге.
📋 Подробности подхода
- Создаем два булевых массива
seen_in_a и seen_in_b длины n + 1 для отслеживания элементов, уже встреченных в A и B.
- Проходим по массивам
A и B одновременно:
- Помечаем текущие элементы
A[i] и B[i] как "увиденные".
- Увеличиваем счетчик общих элементов, если текущий элемент уже был встречен в другом массиве.
- На каждом шаге добавляем текущее значение счетчика общих элементов в результат.
⏱️ Асимптотика
- Временная сложность:
O(n), где n — длина входных массивов. Мы выполняем один проход по массивам.
- Пространственная сложность:
O(n), так как используются два булевых массива для отслеживания.
💻 Исходный код
impl Solution {
pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let n = a.len();
let mut seen_in_a = vec![false; n + 1];
let mut seen_in_b = vec![false; n + 1];
let mut result = Vec::with_capacity(n);
let mut common_count = 0;
for i in 0..n {
// Mark the current element of `a` as seen
seen_in_a[a[i] as usize] = true;
if seen_in_b[a[i] as usize] {
common_count += 1; // Increment if already seen in `b`
}
// Mark the current element of `b` as seen
seen_in_b[b[i] as usize] = true;
if seen_in_a[b[i] as usize] {
common_count += 1; // Increment if already seen in `a`
}
// Append the current common count to the result
result.push(common_count);
}
result
}
}