Leetcode/c++/2965_Find-Missing-and-Repeated-Values.cpp at main · yangfut/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size(), m = n * n;
        vector<int> ans(2);
        vector<bool> freq(m+1);
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                int val = grid[i][j];
                if(freq[val] == true) ans[0] = val;
                else freq[val] = true;
            }
        }

        for(int i = 1; i < m+1; ++i){
            if(freq[i]== false) ans[1] = i;
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        int total = n * n;
        int expectedSum = total * (total+1) / 2;
        int actualSum = 0, twiceNumber = 0, missingNumber = 0;
        vector<bool> visited(total+1);
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                int val = grid[i][j];
                if(visited[val] == true) twiceNumber = val;
                visited[val] = true;
                actualSum += val;
            }
        }

        missingNumber = expectedSum - (actualSum - twiceNumber);
        return {twiceNumber, missingNumber};
    }
};