Cách Tìm Số Bị Lặp và Số Bị Thiếu Trong Ma Trận Nghiệm N

Giới thiệu

Chào các bạn! Hôm nay chúng ta sẽ cùng khám phá một bài toán thú vị về ma trận. Bài toán này không chỉ giúp các bạn nâng cao tư duy lập trình mà còn rèn luyện kỹ năng giải quyết vấn đề.

Bài Toán

Cho một ma trận có kích thước 𝑛×𝑛, trong đó chứa các số nguyên từ 1 đến 𝑛². Trong ma trận này, có một số bị lặp lại và một số khác bị thiếu. Nhiệm vụ của chúng ta là tìm ra hai số này: số bị lặp và số bị thiếu.

Giải Pháp 1: Sử Dụng HashMap

Đầu tiên, chúng ta có thể sử dụng HashMap (hay còn gọi là Dictionary trong Python) để đếm số lần xuất hiện của từng số trong ma trận. Dưới đây là quy trình chi tiết:

1. Khởi tạo HashMap để lưu trữ số lượng xuất hiện của mỗi số.
2. Duyệt toàn bộ ma trận và cập nhật số lần xuất hiện cho mỗi số trong HashMap.
3. Nếu một số xuất hiện nhiều hơn 1 lần, đó là số bị lặp lại.
4. Tính tổng tất cả các số trong ma trận.
5. Dựa trên tổng của dãy số từ 1 đến 𝑛², ta có thể tìm ra số bị thiếu bằng công thức sau:
   missing_num = n² * (n² + 1) / 2 - (sum - duplicate_num)
6. Trả về cặp số (số bị lặp, số bị thiếu).

Code Mẫu:

def findMissingAndRepeatedValues(self, grid: List[List[int]]):
    char_count = defaultdict(int)
    duplicate_num = 0
    total_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]
            total_sum += grid[i][j]

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

Phân Tích Phức Tạp Thời Gian: O(n²)

Giải Pháp 2: Sử Dụng Phân Tích Toán Học

Phương pháp tiếp theo là sử dụng phân tích toán học để giải bài toán theo cách khác:

1. Gọi hai biến a và b lần lượt là số bị lặp và số bị thiếu.
2. Tính tổng của tất cả các phần tử trong ma trận, gọi là sum.
3. 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.
4. Thiết lập hai phương trình:
   • c1 = sum - n² * (n² + 1) / 2
   • c2 = sqrSum - n² * (n² + 1) * (2n² + 1) / 6
5. Giải hệ phương trình để tìm a và b.

Code Mẫu:

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

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

Kết Luận

Thông qua hai cách tiếp cận trên, các bạn có thể dễ dàng tìm ra số bị lặp và số bị thiếu trong một ma trận. Hy vọng bài viết này hữu ích cho các bạn trong việc nâng cao kỹ năng lập trình và giải quyết bài toán!

Nếu bạn có bất kỳ câu hỏi nào, hãy để lại comment bên dưới nhé!
source: viblo