C++程序从字符矩阵中删除行或列重复项

我们得到一个具有行和列的二维矩阵。该矩阵由char数据类型的元素组成。设计了一种方法来删除在其各自的行或列中重复的元素。

在这种方法中，我们检查每个字符是否在其行或列中重复。如果它没有重复，我们保持它与之前一样。

我们可以将每行和每列中出现的数值存储在一个映射中。之后，我们可以再次遍历并获取那些仅在其行和列中出现一次的数值。这将需要额外的空间，并且我们可以通过在其行和列中搜索每个元素来进行时空权衡。我们使用了一个映射来存储字符和计数。

vector<vector<char>> arr = {
   {'A', 'B', 'E', 'G', 'L'},
   {'K', 'M', 'P', 'Q', 'S'},
   {'V', 'W', 'T', 'B', 'O'},
   {'K', 'H', 'O', 'U', 'P'},
   {'P', 'I', 'C', 'Y', 'J'},
   {'F', 'S', 'K', 'E', 'W'},
   {'N', 'L', 'Y', 'G', 'O'},
};
res = solve(arr);

示例（使用Vector ADT）

假设我们有一个包含以下字符的矩阵：

A C E G I
K M O Q S
U W Y B D
K H I N P
R T W X Z
A E I M Q
L O P G A

这里，对于矩阵的第一行，我们不能考虑'A'和'G'，因为它们在各自的列中出现了两次，但我们可以考虑'C'，'E'，'I'。以下是上述示例的C++程序：

#include <iostream>
#include <vector>
#include <map>
using namespace std;
void solve(vector<vector<char>>& arr) {
   vector<map<char, int>> rows(arr.size()), columns(arr[0].size());
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         rows[i][arr[i][j]]++;
         columns[j][arr[i][j]]++;
      }
   }
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         if(rows[i][arr[i][j]] == 1 && columns[j][arr[i][j]] == 1) {
            cout << arr[i][j];
         }
      }
   }
}
int main() {
   vector<vector<char>> arr = {
      {'A', 'C', 'E', 'G', 'I'},
      {'K', 'M', 'O', 'Q', 'S'},
      {'U', 'W', 'Y', 'B', 'D'},
      {'K', 'H', 'I', 'N', 'P'},
      {'R', 'T', 'W', 'X', 'Z'},
      {'A', 'E', 'I', 'M', 'Q'},
      {'L', 'O', 'P', 'G', 'A'},
   };
   solve(arr);
   return 0;
}

输出

CEIMOQSUWYBDHNPRTWXZEMQLOPA

示例（不使用Vector ADT）

#include <bits/stdc++.h>
using namespace std;
int main() {
   int row = 2, column = 8;
   const char* input_array[] = { "ABCDPQST", "ECFDOMUT" };

   bool boolean_array[row][column];
   memset(boolean_array, 0, sizeof(boolean_array));

   for (int i = 0; i < row; i++) {
      for (int j = 0; j < column; j++) {
          
         for (int k = 0; k < column; k++) {
            if (input_array[i][j] == input_array[i][k] && j != k) {
                boolean_array[i][j] = true;
                boolean_array[i][k] = true;
            }
         }
         for (int k = 0; k < row; k++) {
            if (input_array[i][j] == input_array[k][j] && i != k) {
                boolean_array[i][j] = true;
                boolean_array[k][j] = true;
            }
         }
      }
   }
   for (int i = 0; i < row; i++)
   for (int j = 0; j < column; j++)
   if (!boolean_array[i][j])
      printf("%c ", input_array[i][j]);
   return 0;
}

输出

A B C P Q S E C F O M U

结论

我们使用了O(n^2)的复杂度。对于只有小写拉丁字符的情况，映射的log(n)复杂度可以忽略不计，因为只有26个字符。但是对于更多随机字符的字符，这可能会起作用。您可以尝试自己不使用哈希和额外空间来解决此问题。

更新于： 2022年8月10日

431 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习
广告

© . All rights reserved.