Hehehe, chào ae. Welcome to mái chan nồ !.

Bài toán

Cho một ma trận 𝑛×𝑛, trong đó chứa các số từ 1 đến 𝑛2, nhưng có một số bị lặp lại và một số bị thiếu. Nhiệm vụ của chúng ta là tìm ra số bị lặp lại và số bị thiếu.

Cách 1

• Dùng HashMap để đếm số lần xuất hiện
• Duyệt toàn bộ ma trận, sử dụng một hashmap (dictionary) để đếm số lần xuất hiện của mỗi số.
• Nếu một số xuất hiện hơn 1 lần, đó là số bị lặp.
• Tính tổng tất cả các số trong ma trận. Dựa vào tổng của dãy từ 1 1 đến 𝑛 2 n 2 , ta tìm ra số bị thiếu bằng công thức: missing_num = 𝑛 2 ( 𝑛 2 + 1 ) 2 − ( sum − duplicate_num )
• Trả về cặp số ( duplicate , missing ) (duplicate,missing).

Code

Time complexity: O(n^2)

def findMissingAndRepeatedValues(self, grid: List[List[int]]):
        char_count = defaultdict(int)
        duplicate_num = 0
        sum = 0
        for i in range(len(grid)):
            for j in range(len(grid)):
                char_count[grid[i][j]] += 1
                if char_count[grid[i][j]] > 1:
                    duplicate_num = grid[i][j]
                sum += grid[i][j]

        original_sum = pow(len(grid), 2)
        missing_num = original_sum * \
            (original_sum+1) // 2 - (sum - duplicate_num)
        return [duplicate_num, missing_num]

Cách 2:

• Gọi a và b lần lượt là số bị lặp và số bị thiếu
• Tính tổng của tất cả các phần tử trong ma trận, gọi là sum.
• Tính tổng bình phương của tất cả các phần tử trong ma trận, gọi là sqrSum.
• Dựa vào tổng của dãy số tự nhiên 1 đến 𝑛 2 , ta có:
• 
• Ta thiết lập 2 phương trình:
  
• Giải hệ ta được:
  

Code

def findMissingAndRepeatedValues2(self, grid: List[List[int]]):
        sum, sqrSum, n, sqrN = 0, 0, len(grid), len(grid)*len(grid)
        for i in range(n):
            for j in range(n):
                sum += grid[i][j]
                sqrSum += grid[i][j] * grid[i][j]

        c1 = sum - sqrN*(sqrN+1) // 2
        c2 = sqrSum - sqrN*(sqrN+1)*(sqrN*2+1) // 6
        return [(c2//c1 + c1) // 2, (c2//c1 - c1) // 2]