สมมติว่าเรามีเมทริกซ์ขององค์ประกอบเฉพาะและผลรวม เราต้องหาคู่ทั้งหมดจากเมทริกซ์ที่มีผลรวมเท่ากับผลรวมที่กำหนด ที่นี่ แต่ละองค์ประกอบของคู่จะถูกนำมาจากแถวที่ต่างกัน
ดังนั้นหากอินพุตเป็น −
| 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]
-
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
สำหรับ j ในช่วง i + 1 ถึง n ทำ
-
ต่ำ :=0, สูง :=n - 1
-
ในขณะที่ต่ำ
=0 ทำ -
ถ้า (เมทริกซ์[i ต่ำ] + เมทริกซ์[j สูง]) เท่ากับผลรวม ดังนั้น
-
คู่ :=สร้างคู่โดยใช้ (matrix[i, low],matrix[j, high])
-
ใส่คู่ที่ส่วนท้ายของ res
-
ต่ำ :=ต่ำ + 1
-
สูง :=สูง - 1
-
-
มิฉะนั้น
-
ถ้า (เมทริกซ์[i][ต่ำ] + เมทริกซ์[j][สูง]) <ผลรวม ดังนั้น
-
ต่ำ :=ต่ำ + 1
-
-
มิฉะนั้น
-
สูง :=สูง - 1
-
-
-
-
-
-
ผลตอบแทน
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)]
