LeetCode 2965: Find Missing and Repeated Values (Frequency Counting on 1..n²)
LeetCode 2965MatrixCountingToday we solve LeetCode 2965 - Find Missing and Repeated Values.
Source: https://leetcode.com/problems/find-missing-and-repeated-values/
English
Problem Summary
You are given an n x n matrix that should contain all numbers from 1 to n² exactly once. But one value appears twice and one value is missing. Return [repeated, missing].
Key Insight
The value range is compact and known: exactly 1..n². So we can count frequencies directly. The number with count 2 is repeated, and the one with count 0 is missing.
Algorithm
- Let limit = n * n, create freq[limit + 1] initialized to 0.
- Traverse every cell in the matrix and increment freq[value].
- Scan 1..limit: count 2 gives repeated, count 0 gives missing.
- Return [repeated, missing].
Complexity Analysis
There are n² elements.
Time: O(n²).
Space: O(n²) for the frequency array.
Common Pitfalls
- Returning the pair in the wrong order (must be repeated first).
- Building frequency array with wrong size and losing value n².
- Forgetting matrix values are 1-indexed while many arrays are 0-indexed.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] findMissingAndRepeatedValues(int[][] grid) {
int n = grid.length;
int limit = n * n;
int[] freq = new int[limit + 1];
for (int[] row : grid) {
for (int value : row) {
freq[value]++;
}
}
int repeated = -1, missing = -1;
for (int value = 1; value <= limit; value++) {
if (freq[value] == 2) repeated = value;
else if (freq[value] == 0) missing = value;
}
return new int[]{repeated, missing};
}
}func findMissingAndRepeatedValues(grid [][]int) []int {
n := len(grid)
limit := n * n
freq := make([]int, limit+1)
for _, row := range grid {
for _, value := range row {
freq[value]++
}
}
repeated, missing := -1, -1
for value := 1; value <= limit; value++ {
if freq[value] == 2 {
repeated = value
} else if freq[value] == 0 {
missing = value
}
}
return []int{repeated, missing}
}class Solution {
public:
vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
int n = (int)grid.size();
int limit = n * n;
vector<int> freq(limit + 1, 0);
for (auto &row : grid) {
for (int value : row) {
freq[value]++;
}
}
int repeated = -1, missing = -1;
for (int value = 1; value <= limit; ++value) {
if (freq[value] == 2) repeated = value;
else if (freq[value] == 0) missing = value;
}
return {repeated, missing};
}
};class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
limit = n * n
freq = [0] * (limit + 1)
for row in grid:
for value in row:
freq[value] += 1
repeated = missing = -1
for value in range(1, limit + 1):
if freq[value] == 2:
repeated = value
elif freq[value] == 0:
missing = value
return [repeated, missing]var findMissingAndRepeatedValues = function(grid) {
const n = grid.length;
const limit = n * n;
const freq = new Array(limit + 1).fill(0);
for (const row of grid) {
for (const value of row) {
freq[value]++;
}
}
let repeated = -1, missing = -1;
for (let value = 1; value <= limit; value++) {
if (freq[value] === 2) repeated = value;
else if (freq[value] === 0) missing = value;
}
return [repeated, missing];
};中文
题目概述
给你一个 n x n 矩阵，理论上应当恰好包含 1..n² 的每个数字各一次。但现在有一个数字重复出现了两次，同时有一个数字缺失。返回 [重复值, 缺失值]。
核心思路
值域是连续且已知的：1..n²。最直接的方法就是频次数组计数。出现次数为 2 的是重复值，出现次数为 0 的是缺失值。
算法步骤
- 设 limit = n * n，创建长度为 limit + 1 的 freq 数组。
- 遍历矩阵中每个元素 value，执行 freq[value]++。
- 扫描 1..limit：freq == 2 记为重复值，freq == 0 记为缺失值。
- 返回 [重复值, 缺失值]。
复杂度分析
矩阵共有 n² 个元素。
时间复杂度：O(n²)。
空间复杂度：O(n²)（频次数组）。
常见陷阱
- 返回顺序写反（题目要求先重复值、后缺失值）。
- 频次数组长度开小，导致 n² 越界或漏统计。
- 忽略题目值是从 1 开始编号。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] findMissingAndRepeatedValues(int[][] grid) {
int n = grid.length;
int limit = n * n;
int[] freq = new int[limit + 1];
for (int[] row : grid) {
for (int value : row) {
freq[value]++;
}
}
int repeated = -1, missing = -1;
for (int value = 1; value <= limit; value++) {
if (freq[value] == 2) repeated = value;
else if (freq[value] == 0) missing = value;
}
return new int[]{repeated, missing};
}
}func findMissingAndRepeatedValues(grid [][]int) []int {
n := len(grid)
limit := n * n
freq := make([]int, limit+1)
for _, row := range grid {
for _, value := range row {
freq[value]++
}
}
repeated, missing := -1, -1
for value := 1; value <= limit; value++ {
if freq[value] == 2 {
repeated = value
} else if freq[value] == 0 {
missing = value
}
}
return []int{repeated, missing}
}class Solution {
public:
vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
int n = (int)grid.size();
int limit = n * n;
vector<int> freq(limit + 1, 0);
for (auto &row : grid) {
for (int value : row) {
freq[value]++;
}
}
int repeated = -1, missing = -1;
for (int value = 1; value <= limit; ++value) {
if (freq[value] == 2) repeated = value;
else if (freq[value] == 0) missing = value;
}
return {repeated, missing};
}
};class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
limit = n * n
freq = [0] * (limit + 1)
for row in grid:
for value in row:
freq[value] += 1
repeated = missing = -1
for value in range(1, limit + 1):
if freq[value] == 2:
repeated = value
elif freq[value] == 0:
missing = value
return [repeated, missing]var findMissingAndRepeatedValues = function(grid) {
const n = grid.length;
const limit = n * n;
const freq = new Array(limit + 1).fill(0);
for (const row of grid) {
for (const value of row) {
freq[value]++;
}
}
let repeated = -1, missing = -1;
for (let value = 1; value <= limit; value++) {
if (freq[value] === 2) repeated = value;
else if (freq[value] === 0) missing = value;
}
return [repeated, missing];
};
Comments