2965. Find Missing and Repeated Values
https://leetcode.com/problems/find-missing-and-repeated-values/
一个n*n矩阵 填入n*n数字
但多一个a(出现两次)少一个b(出现零次)
求[a, b]
Solution:
数学题
1.不考虑ab情况 矩阵总和是个d=1的等差数列
d=1的等差数列总和是 n^2(n^2 + 1) / 2 视为 sum0
题目矩阵多a少b所以是 sum0 + a - b = sum
2. 不考虑ab情况 矩阵平方和
d=1的等差数列平方和是 n^1(n^1 + 1)(2n^2 + 1) / 6 视为 sum_of_square0
题目矩阵多a少b所以是 sum_of_square0 + a^2 - b^2 = sum_of_square
解联立方程式就能得到答案
联立1: sum0 - sum = a - b
联立2: sos - sos0 = a^2 - b^2 = (a + b)(a - b)
把1代入2: sos - sos0 = (a + b)(sum0 - sum)
化成3: (sos - sos0)/(sum0 - sum) = a + b
用1跟3相加跟相减解a,b
a = [(sos - sos0)/(sum0 - sum) + (sum0 - sum)] / 2
b = [(sos - sos0)/(sum0 - sum) - (sum0 - sum)] / 2
计算之后得解答
Code:
impl Solution {
fn find_missing_and_repeated_values(grid: Vec<Vec<i32>>) -> Vec<i32> {
let n = grid.len();
let n2 = n * n;
let expected_sum = (n2 * (n2 + 1) / 2) as i64;
let expected_sum_sq = (n2 * (n2 + 1) * (2 * n2 + 1) / 6) as i64;
let mut actual_sum: i64 = 0;
let mut actual_sum_sq: i64 = 0;
for i in 0..n {
for j in 0..n {
let val = grid[i][j] as i64;
actual_sum += val;
actual_sum_sq += val * val;
}
}
let x = actual_sum - expected_sum;
let y = (actual_sum_sq - expected_sum_sq) / x;
let a = ((x + y) / 2) as i32;
let b = ((y - x) / 2) as i32;
vec![a, b]
}
}