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.