找出缺失和重复的数字

100149. 找出缺失和重复的数字

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n²] 范围内。除了 a 出现两次，b 缺失之外，每个整数都 恰好出现一次 。

任务是找出重复的数字a 和缺失的数字 b 。

返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。

示例 1：

输入：grid = [[1,3],[2,2]]
输出：[2,4]
解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。

示例 2：

输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
输出：[9,5]
解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。

提示：

2 <= n == grid.length == grid[i].length <= 50
1 <= grid[i][j] <= n * n
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) { } };

golang 解法, 执行用时: 10 ms, 内存消耗: 5 MB, 提交时间: 2024-05-31 09:28:34

// 数学
func findMissingAndRepeatedValues(grid [][]int) []int {
	n := len(grid)
	m := n * n
	d1 := -m * (m + 1) / 2
	d2 := -m * (m + 1) * (m*2 + 1) / 6
	for _, row := range grid {
		for _, x := range row {
			d1 += x
			d2 += x * x
		}
	}
	return []int{(d2/d1 + d1) / 2, (d2/d1 - d1) / 2}
}

// 位运算2
func findMissingAndRepeatedValues2(grid [][]int) []int {
    n := len(grid)
    xorAll := 0
    for _, row := range grid {
        for _, x := range row {
            xorAll ^= x
        }
    }
    if n%2 > 0 {
        xorAll ^= 1
    } else {
        xorAll ^= n * n
    }
    shift := bits.TrailingZeros(uint(xorAll))

    ans := make([]int, 2)
    for x := 1; x <= n*n; x++ {
        ans[x>>shift&1] ^= x
    }
    for _, row := range grid {
        for _, x := range row {
            ans[x>>shift&1] ^= x
        }
    }

    for _, row := range grid {
        if slices.Contains(row, ans[0]) {
            return ans
        }
    }
    return []int{ans[1], ans[0]}
}

python3 解法, 执行用时: 58 ms, 内存消耗: 17 MB, 提交时间: 2024-05-31 09:27:52

class Solution:
    # 位运算
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        xor_all = reduce(xor, (x for row in grid for x in row)) ^ (1 if n % 2 else n * n)
        shift = xor_all.bit_length() - 1

        ans = [0, 0]
        for x in range(1, n * n + 1):
            ans[x >> shift & 1] ^= x
        for row in grid:
            for x in row:
                ans[x >> shift & 1] ^= x

        return ans if ans[0] in (x for row in grid for x in row) else ans[::-1]
        
    # 数学
    def findMissingAndRepeatedValues2(self, grid: List[List[int]]) -> List[int]:
        m = len(grid) ** 2
        d1 = sum(x for row in grid for x in row) - m * (m + 1) // 2
        d2 = sum(x * x for row in grid for x in row) - m * (m + 1) * (m * 2 + 1) // 6
        return [(d2 // d1 + d1) // 2, (d2 // d1 - d1) // 2]

javascript 解法, 执行用时: 69 ms, 内存消耗: 52.1 MB, 提交时间: 2024-05-31 09:27:06

/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var findMissingAndRepeatedValues = function(grid) {
    const n = grid.length;
    const cnt = Array(n * n + 1).fill(0);
    for (const row of grid) {
        for (const x of row) {
            cnt[x]++;
        }
    }

    const ans = Array(2);
    for (let i = 1; i <= n * n; i++) {
        if (cnt[i] === 2) {
            ans[0] = i; // 出现两次的数
        } else if (cnt[i] === 0) {
            ans[1] = i; // 出现零次的数
        }
    }
    return ans;
};

golang 解法, 执行用时: 11 ms, 内存消耗: 5.7 MB, 提交时间: 2024-05-31 09:26:24

func findMissingAndRepeatedValues(grid [][]int) []int {
    n := len(grid)
    cnt := make([]int, n * n + 1)
    for _, row := range grid {
        for _, x := range row {
            cnt[x]++
        }
    }

    ans := []int{0, 0}
    for i := 1; i <= n * n; i++ {
        if cnt[i] == 2 {
            ans[0] = i
        } else if cnt[i] == 0 {
            ans[1] = i
        }
    }
    return ans
}

python3 解法, 执行用时: 56 ms, 内存消耗: 16.5 MB, 提交时间: 2023-12-17 23:31:10

'''
数组统计每个数出现次数
'''
class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        cnt = [0] * (n * n + 1)
        for row in grid:
            for x in row:
                cnt[x] += 1

        ans = [0, 0]
        for i in range(1, n * n + 1):
            if cnt[i] == 2:
                ans[0] = i
            elif cnt[i] == 0:
                ans[1] = i
        return ans

java 解法, 执行用时: 1 ms, 内存消耗: 43.7 MB, 提交时间: 2023-12-17 23:31:27

public class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int[] cnt = new int[n * n + 1];
        for (int[] row : grid) {
            for (int x : row) {
                cnt[x]++;
            }
        }

        int[] ans = new int[2];
        for (int i = 1; i <= n * n; i++) {
            if (cnt[i] == 2) {
                ans[0] = i;
            } else if (cnt[i] == 0) {
                ans[1] = i;
            }
        }
        return ans;
    }
}

cpp 解法, 执行用时: 20 ms, 内存消耗: 22.1 MB, 提交时间: 2023-12-17 23:31:44

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>> &grid) {
        int n = grid.size();
        vector<int> cnt(n * n + 1);
        for (const vector<int> &row: grid) {
            for (int x: row) {
                cnt[x]++;
            }
        }

        vector<int> ans(2, 0);
        for (int i = 1; i <= n * n; i++) {
            if (cnt[i] == 2) {
                ans[0] = i;
            } else if (cnt[i] == 0) {
                ans[1] = i;
            }
        }
        return ans;
    }
};

rust 解法, 执行用时: 12 ms, 内存消耗: 2.3 MB, 提交时间: 2023-12-17 23:33:51

use std::collections::HashSet;
impl Solution {
    pub fn find_missing_and_repeated_values(grid: Vec<Vec<i32>>) -> Vec<i32> {
        let n = grid.len() as i32;
        let mut st = HashSet::new();
        let mut res = vec![0; 2];
        // 找重复
        for x in grid.iter().flatten() {
            if st.contains(x) {
                res[0] = *x;
            }
            st.insert(*x);
        }
        // 找缺失
        res[1] = (1..=n * n).find(|x| !st.contains(x)).unwrap();
        res
    }
}

上一题

下一题

详情