Tìm các phần tử riêng biệt chung cho tất cả các hàng của ma trận trong Python

Giả sử chúng ta có một ma trận vuông cấp m x m; chúng ta cần tìm tất cả các phần tử riêng biệt chung cho tất cả các hàng của ma trận cho trước.

Ví dụ, nếu đầu vào như sau:

thì đầu ra sẽ là [2, 4, 15].

Giải thuật

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

• Định nghĩa hàm sortRows() để sắp xếp từng hàng của ma trận.
• Lấy số hàng n.
• Sắp xếp từng hàng matrix[i].
• Trong hàm chính:
  • Khởi tạo mảng current_idx kích thước n với giá trị 0.
  • Duyệt qua các phần tử của hàng đầu tiên (đã sắp xếp).
  • Với mỗi giá trị, kiểm tra xem nó có xuất hiện trong tất cả các hàng còn lại không bằng cách di chuyển con trỏ current_idx[i].
  • Nếu giá trị xuất hiện trong mọi hàng, in ra giá trị đó.

Ví dụ minh họa (Python)

MAX = 100
def sortRows(matrix):
    n = len(matrix)
    for i in range(0, n):
        matrix[i].sort()

def find_common(matrix):
    n = len(matrix)
    sortRows(matrix)
    current_idx = [0] * n
    for i in range(0, n):
        current_idx[i] = 0
    f = 0
    while current_idx[0] < n:
        value = matrix[0][current_idx[0]]
        present = True
        for i in range(1, n):
            while current_idx[i] < n and matrix[i][current_idx[i]] <= value:
                current_idx[i] += 1
            if matrix[i][current_idx[i] - 1] != value:
                present = False
            if current_idx[i] == n:
                f = 1
                break
        if present:
            print(value, end=", ")
        if f == 1:
            break
        current_idx[0] += 1

mat = [
    [13, 2, 15, 4, 17],
    [15, 3, 2, 4, 36],
    [15, 2, 15, 4, 12],
    [15, 26, 4, 3, 2],
    [2, 19, 4, 22, 15]
]
find_common(mat)

Đầu vào

[[13, 2, 15, 4, 17], [15, 3, 2, 4, 36], [15, 2, 15, 4, 12], [15, 26, 4, 3, 2], [2, 19, 4, 22, 15]]

Đầu ra

2, 4, 15,