Giả sử chúng ta có một ma trận gồm các phần tử duy nhất và một tổng; chúng ta phải tìm tất cả các cặp từ ma trận có tổng bằng tổng đã cho. Ở đây, mỗi phần tử của cặp sẽ được lấy từ các hàng khác nhau.
Vì vậy, nếu đầu vào giống như -
| 2 | 4 | 3 | 5 |
| 6 | 9 | 8 | 7 |
| 10 | 11 | 14 | 12 |
| 13 | 1 | 15 | 16 |
sum =13, thì đầu ra sẽ là [(2, 11), (4, 9), (3, 10), (5, 8), (12, 1)]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
res:=một danh sách mới
-
n:=kích thước của ma trận
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
sắp xếp ma trận danh sách [i]
-
-
đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện
-
đối với j trong phạm vi i + 1 đến n, thực hiện
-
thấp:=0, cao:=n - 1
-
trong khi thấp
=0, thực hiện -
nếu (ma trận [i, thấp] + ma trận [j, cao]) giống với tổng, thì
-
cặp:=tạo cặp bằng cách sử dụng (ma trận [i, thấp], ma trận [j, cao])
-
chèn cặp vào cuối res
-
thấp:=thấp + 1
-
cao:=cao - 1
-
-
nếu không,
-
if (matrix [i] [low] + matrix [j] [high])
-
thấp:=thấp + 1
-
-
nếu không,
-
cao:=cao - 1
-
-
-
-
-
-
trả lại res
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
MAX = 100 def sum_pair(matrix, sum): res = [] n = len(matrix) for i in range(n): matrix[i].sort() for i in range(n - 1): for j in range(i + 1, n): low = 0 high = n - 1 while (low < n and high >= 0): if ((matrix[i][low] + matrix[j][high]) == sum): pair = (matrix[i][low],matrix[j][high]) res.append(pair) low += 1 high -= 1 else: if ((matrix[i][low] + matrix[j][high]) < sum): low += 1 else: high -= 1 return res sum = 13 matrix = [ [2, 4, 3, 5], [6, 9, 8, 7], [10, 11, 14, 12], [13, 1, 15, 16]] print(sum_pair(matrix, sum))
Đầu vào
[[2, 4, 3, 5], [6, 9, 8, 7], [10, 11, 14, 12], [13, 1, 15, 16]] sum = 13
Đầu ra
[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]