고유한 요소와 합계로 구성된 행렬이 있다고 가정합니다. 합이 주어진 합과 같은 행렬에서 모든 쌍을 찾아야 합니다. 여기에서 쌍의 각 요소는 다른 행에서 가져옵니다.
따라서 입력이 다음과 같으면 -
| 2 | 4 | 3 | 5 |
| 6 | 9 | 8 | 7 |
| 10 | 11 | 14 | 12 |
| 13 | 1 | 15 | 16 |
sum =13이면 출력은 [(2, 11), (4, 9), (3, 10), (5, 8), (12, 1)]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
res :=새 목록
-
n :=행렬의 크기
-
0에서 n 사이의 i에 대해 수행
-
목록 행렬 정렬[i]
-
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
i + 1에서 n 사이의 j에 대해 수행
-
낮음 :=0, 높음 :=n - 1
-
낮음
=0인 동안 수행 -
(matrix[i, low] + matrix[j, high])가 합과 같으면
-
pair :=(matrix[i, low],matrix[j, high])
를 사용하여 쌍을 만듭니다. -
res의 끝에 쌍 삽입
-
낮음 :=낮음 + 1
-
높음 :=높음 - 1
-
-
그렇지 않으면
-
if (matrix[i][low] + matrix[j][high])
-
낮음 :=낮음 + 1
-
-
그렇지 않으면
-
높음 :=높음 - 1
-
-
-
-
-
-
반환 해상도
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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))
입력
[[2, 4, 3, 5], [6, 9, 8, 7], [10, 11, 14, 12], [13, 1, 15, 16]] sum = 13
출력
[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]