查找具有给定总和的对，以便该对的元素位于不同的行中
原文： https://www.geeksforgeeks.org/find-pairs-given-sum-elements-pair-different-rows/
给定不同值和总和的矩阵。 任务是找到给定总和等于给定总和的所有对。 对中的每个元素必须来自不同的行，即； 对不得位于同一行。
示例：
Input : mat[4][4] = {{1, 3, 2, 4},
{5, 8, 7, 6},
{9, 10, 13, 11},
{12, 0, 14, 15}}
sum = 11
Output: (1, 10), (3, 8), (2, 9), (4, 7), (11, 0)
方法 1（简单）：
解决此问题的简单方法是一个一个接一个地获取所有行的每个元素，并从矩阵中的下一行开始查找对。 该方法的时间复杂度将为O(n ^ 4)。
方法 2（使用排序）：
-
按升序对所有行进行排序。 该预处理的时间复杂度将为
O(n ^ 2 logn)。 -
现在，我们将逐行选择每一行，并在当前行之后的其余行中找到对元素。
-
取两个迭代器
left和right。left迭代器指向当前第i行的左侧，right迭代器指向下一个我们要在其中查找对元素的第j行的右侧。 -
如果
mat[i][left] + mat[j][right] < sum，则left++，即； 向右移第i行，否则right++，即； 在第j行向左侧移动。
C++
// C++ program to find a pair with given sum such that
// every element of pair is in different rows.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Function to find pair for given sum in matrix
// mat[][] --> given matrix
// n --> order of matrix
// sum --> given sum for which we need to find pair
void pairSum(int mat[][MAX], int n, int sum)
{
// First sort all the rows in ascending order
for (int i=0; i<n; i++)
sort(mat[i], mat[i]+n);
// Select i'th row and find pair for element in i'th
// row in j'th row whose summation is equal to given sum
for (int i=0; i<n-1; i++)
{
for (int j=i+1; j<n; j++)
{
int left = 0, right = n-1;
while (left<n && right>=0)
{
if ((mat[i][left] + mat[j][right]) == sum)
{
cout << "(" << mat[i][left]
<< ", "<< mat[j][right] << "), ";
left++;
right--;
}
else
{
if ((mat[i][left] + mat[j][right]) < sum)
left++;
else
right--;
}
}
}
}
}
// Driver program to run the case
int main()
{
int n = 4, sum = 11;
int mat[][MAX] = {{1, 3, 2, 4},
{5, 8, 7, 6},
{9, 10, 13, 11},
{12, 0, 14, 15}};
pairSum(mat, n, sum);
return 0;
}
Java
// Java program to find a pair with
// given sum such that every element
// of pair is in different rows.
import java.util.Arrays;
class GFG {
static final int MAX = 100;
// Function to find pair for given sum in
// matrix mat[][] --> given matrix
// n --> order of matrix
// sum --> given sum for which we need to find pair
static void pairSum(int mat[][], int n, int sum) {
// First sort all the rows in ascending order
for (int i = 0; i < n; i++)
Arrays.sort(mat[i]);
// Select i'th row and find pair for element in i'th
// row in j'th row whose summation is equal to given sum
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int left = 0, right = n - 1;
while (left < n && right >= 0) {
if ((mat[i][left] + mat[j][right]) == sum) {
System.out.print("(" + mat[i][left] + ", " +
mat[j][right] + "), ");
left++;
right--;
}
else {
if ((mat[i][left] + mat[j][right]) < sum)
left++;
else
right--;
}
}
}
}
}
// Driver code
public static void main(String[] args) {
int n = 4, sum = 11;
int mat[]
[] = {{1 , 3, 2, 4},
{5 , 8, 7, 6},
{9 , 10, 13, 11},
{12, 0, 14, 15}};
pairSum(mat, n, sum);
}
}
// This code is contributed by Anant Agarwal.
Python 3
# Python 3 program to find a pair with
# given sum such that every element of
# pair is in different rows.
MAX = 100
# Function to find pair for given
# sum in matrix mat[][] --> given matrix
# n --> order of matrix
# sum --> given sum for which we
# need to find pair
def pairSum(mat, n, sum):
# First sort all the rows
# in ascending order
for i in range(n):
mat[i].sort()
# Select i'th row and find pair for
# element in i'th row in j'th row
# whose summation is equal to given sum
for i in range(n - 1):
for j in range(i + 1, n):
left = 0
right = n - 1
while (left < n and right >= 0):
if ((mat[i][left] + mat[j][right]) == sum):
print( "(", mat[i][left],
", ", mat[j][right], "), ",
end = " ")
left += 1
right -= 1
else:
if ((mat[i][left] +
mat[j][right]) < sum):
left += 1
else:
right -= 1
# Driver Code
if __name__ == "__main__":
n = 4
sum = 11
mat = [[1, 3, 2, 4],
[5, 8, 7, 6],
[9, 10, 13, 11],
[12, 0, 14, 15]]
pairSum(mat, n, sum)
# This code is contributed
# by ChitraNayal
输出：
(1, 10), (3, 8), (2, 9), (4, 7), (11, 0)
时间复杂度：O(n ^ 2 logn + n ^ 3)。
辅助空间：O(1)。
方法 3（散列）：
-
创建一个空的哈希表，并在哈希中将矩阵的所有元素存储为键，并将其位置存储为值。
-
再次遍历矩阵以检查每个元素在散列表中是否存在。 如果存在，则比较行号。 如果行号不同，则打印该对。
CPP
// C++ program to find pairs with given sum such
// the two elements of pairs are from different rows
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Function to find pair for given sum in matrix
// mat[][] --> given matrix
// n --> order of matrix
// sum --> given sum for which we need to find pair
void pairSum(int mat[][MAX], int n, int sum)
{
// Create a hash and store all elements of matrix
// as keys, and row and column numbers as values
unordered_map<int, pair<int, int> > hm;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
hm[mat[i][j]] = make_pair(i, j);
// Traverse the matrix again to check for every
// element whether its pair exists or not.
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
// Look for remaining sum in hash
int remSum = sum - mat[i][j];
auto it = hm.find(remSum); // it is an iterator
// of unordered_map type
// If an element with value equal to remaining sum exists
if (it != hm.end())
{
// Find row and column numbers of element with
// value equal to remaining sum.
pair<int, int> p = it->second;
int row = p.first, col = p.second;
// If row number of pair is not same as current
// row, then print it as part of result.
// Second condition is there to make sure that a
// pair is printed only once.
if (row != i && row > i)
cout << "(" << mat[i][j] << ", "
<< mat[row][col] << "), ";
}
}
}
}
// Driver program
int main()
{
int n = 4, sum = 11;
int mat[][MAX]= {{1, 3, 2, 4},
{5, 8, 7, 6},
{9, 10, 13, 11},
{12, 0, 14, 15}};
pairSum(mat, n, sum);
return 0;
}
Output :
(1, 10), (3, 8), (2, 9), (4, 7), (11, 0),
重要的是，当我们遍历一个矩阵时，一对可能会被打印两次。 为了确保一对仅打印一次，我们检查从哈希表中选取的其他元素的行号是否大于当前元素的行号。
时间复杂度：假设哈希表插入和搜索操作花费O(1)时间，则 O(n^2)。
版权属于：月萌API www.moonapi.com，转载请注明出处
