C++程序：用行或列的最大公约数替换矩阵的每个元素

在这个方法中，我们需要用给定矩阵中每一行和每一列的最大公约数(GCD)来替换矩阵中的每个元素。

让我们看一些输入场景 -

假设我们得到一个m*n维的二维矩阵：

Input:
[[3, 2, 1, 4]
[7, 6, 2, 8]
[14, 20, 25, 17]];

在上面的矩阵中，第1行 gcd(3, 2, 1, 4) = 1，第2列 gcd(3, 7, 14) = 1。所以元素2（第1行第2列）变为最大值(1, 1) = 1。对所有元素依次执行此操作，我们的输出结果应该变为

Result: [
   [1, 2, 1, 1]
   [1, 2, 1, 1]
   [1, 2, 1, 1]
]

再来看一个m*n维的二维矩阵：

Input:
[[3, 2, 5, 4]
[6, 6, 15, 8]
[12, 20, 25, 16]];

在上面的矩阵中，第1行 gcd(3, 2, 5, 4) = 1，第2列 gcd(2, 6, 20) = 2。所以元素2（第1行第2列）变为最大值(1, 2) = 2。对所有元素重复此过程，我们的输出将是 -

Result: [
  [3 2 5 4]
  [3 2 5 4]
  [3 2 5 4]
]

算法

  • 声明了两个函数 GCDArrayRow 和 GCDArrayColumn，分别用于查找行和列中元素的最大公约数。

  • 找到第 i 行和第 j 列的最大公约数，以替换 matrix[i, j] 元素。

  • 对矩阵中的每个元素重复此过程，更新后的矩阵作为输出结果打印。

示例

以下是用 C++ 实现的替换矩阵每个元素为行或列最大公约数的示例 -

在这个程序中，我们可以创建两个数组，称为GCDArrayRow 和GCDArrayColumn，分别存储各行和各列的公约数。在存储所有行和列的公约数后，我们可以遍历数组并逐个计算每个元素的最大值。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve(vector<vector<int>>& arr) {
   vector<int> GCDArrayRow(arr.size(), 0), GCDArrayColumn(arr[0].size(), 0);
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         GCDArrayRow[i] = __gcd(GCDArrayRow[i], arr[i][j]);
         GCDArrayColumn[j] = __gcd(GCDArrayColumn[j], arr[i][j]);
      }
   }
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         arr[i][j] = max(GCDArrayColumn[j], GCDArrayRow[i]);
      }
   }
}
void printArray(vector<vector<int>>& arr) {
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         cout << arr[i][j] << " ";
      }
      cout << "\n";
   }
   cout << "\n";
}
int main() {
   vector<vector<int>> arr = {
      {2, 6, 4, 8},
      {4, 6, 3, 9},
      {7, 21, 28, 7}
   };
   printArray(arr);
   solve(arr);
   printArray(arr);
   return 0;
}

输出

2 6 4 8
4 6 3 9
7 21 28 7


2 3 2 2
1 3 1 1
7 7 7 7

结论

因此，我们可以观察到，创建额外的行和列数组可以帮我们完成工作。我们预先计算每行和每列的 GCD，然后遍历并查找两者的最大值。算法库在 GCD 的内置函数 __gcd 函数中计算 GCD。我们也可以根据欧几里得算法编写我们自己的 GCD 计算函数。

更新于: 2022年8月10日

392 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告

© . All rights reserved.