在Python中查找元素对，使其和等于给定值，且元素位于不同的行

假设我们有一个包含唯一元素的矩阵和一个目标和；我们需要找到矩阵中所有和等于目标和的元素对。这里，每一对元素都必须来自不同的行。

例如：

2435
6987
10111412
1311516

目标和 = 13，则输出为 [(2, 11), (4, 9), (3, 10), (5, 8), (12, 1)]

为了解决这个问题，我们将遵循以下步骤：

  • res := 一个新的列表

  • n := 矩阵的行数

  • 对于 i 从 0 到 n-1：

    • 对列表 matrix[i] 进行排序

  • 对于 i 从 0 到 n-1：

    • 对于 j 从 i+1 到 n-1：

      • low := 0, high := n - 1

      • 当 low < n 且 high >= 0：

        • 如果 (matrix[i][low] + matrix[j][high]) 等于目标和，则

          • pair := 使用 (matrix[i][low], matrix[j][high]) 创建一个元素对

          • 将 pair 添加到 res 的末尾

          • low := low + 1

          • high := high - 1

        • 否则：

          • 如果 (matrix[i][low] + matrix[j][high]) < 目标和，则

            • low := low + 1

          • 否则：

            • high := high - 1

  • low := low + 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)]

更新于: 2020年8月19日

119 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告