Ссылка на задачу — 2965. Find Missing and Repeated Values.
📌 Описание задачи
Дан n×n целочисленный массив grid, содержащий числа от 1 до n².
Одно число повторяется дважды (a), а одно отсутствует (b).
Нужно найти их.
💡 Идея
Мы можем использовать математические свойства сумм чисел:
Разница между ожидаемыми и фактическими значениями позволит выразить a и b через систему уравнений.
🚀 Детали подхода
- Вычисляем ожидаемую сумму и ожидаемую сумму квадратов для чисел от
1 до n².
- Проходим по
grid, вычисляя фактическую сумму и фактическую сумму квадратов.
- Находим промежуточные величины для системы уравнений:
(a - b) = sum_diff(a² - b²) = sum_sq_diff(a + b) = sum_sq_diff / sum_diff.
- Решаем систему уравнений относительно
a и b.
⏱ Асимптотика
- Время:
O(n²), так как проходим по всем элементам один раз (Фактически это линейное время относительно входных данных).
- Память:
O(1), используем только несколько переменных.
📝 Исходный код
impl Solution {
pub fn find_missing_and_repeated_values(grid: Vec<Vec<i32>>) -> Vec<i32> {
let n = grid.len() as i64;
let nn = n * n;
// Expected sum and sum of squares for numbers 1 to n^2
let expected_sum = nn * (nn + 1) / 2;
let expected_sum_squares = nn * (nn + 1) * (2 * nn + 1) / 6;
// Compute actual sum and sum of squares in a single pass
let (sum_actual, sum_sq_actual) = grid.into_iter()
.flatten()
.fold((0, 0), |(sum, sum_sq), val| {
let val = val as i64;
(sum + val, sum_sq + val * val)
});
// Differences between actual and expected values
let sum_diff = sum_actual - expected_sum; // (a - b)
let sum_sq_diff = sum_sq_actual - expected_sum_squares; // (a^2 - b^2)
// Compute (a + b)
let sum_pair = sum_sq_diff / sum_diff;
// Solve for a (repeated number) and b (missing number)
let a: i32 = ((sum_pair + sum_diff) / 2) as _;
let b: i32 = ((sum_pair - sum_diff) / 2) as _;
vec![a, b]
}
}
Tags: #rust #algorithms #math