資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究找出 C++ 中的矩陣所有行中公有的不同元素
概念
對於給定的 m x m 矩陣，問題是確定矩陣所有行共有的所有不同元素。因此，可以以任何順序顯示元素。
輸入
mat[][] = { {13, 2, 15, 4, 17},
{15, 3, 2, 4, 36},
{15, 2, 15, 4, 12},
{15, 26, 4, 3, 2},
{2, 19, 4, 22, 15}
}輸出
2 4 15
方法
第一個方法：實現三個巢狀迴圈。驗證第 1 行中的元素是否存在於所有後續行中。這裡的 time 複雜度為 O(m^3)。可能需要額外的空間來控制重複元素。
第二個方法：單獨按遞增順序對矩陣的所有行進行排列或排序。然後，我們實現確定 3 個已排序陣列中公有元素問題的一種改進方法。以下給出了它的實現。
例
// C++ implementation to find distinct elements
// common to all rows of a matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX1 = 100;
// Shows function to individually sort
// each row in increasing order
void sortRows1(int mat1[][MAX1], int m){
for (int i=0; i<m; i++)
sort(mat1[i], mat1[i] + m);
}
// Shows function to find all the common elements
void findAndPrintCommonElements1(int mat1[][MAX1], int m){
//Used to sort rows individually
sortRows1(mat1, m);
// Shows current column index of each row is stored
// from where the element is being searched in
// that row
int curr_index1[m];
memset(curr_index1, 0, sizeof(curr_index1));
int f = 0;
for (; curr_index1[0]<m; curr_index1[0]++){
//Indicates value present at the current column index
// of 1st row
int value1 = mat1[0][curr_index1[0]];
bool present1 = true;
//Indicates 'value' is being searched in all the
// subsequent rows
for (int i=1; i<m; i++){
// Used to iterate through all the elements of
// the row from its current column index
// till an element greater than the 'value'
// is found or the end of the row is
// encountered
while (curr_index1[i] < m &&
mat1[i][curr_index1[i]] <= value1)
curr_index1[i]++;
// Now if the element was not present at the column
// before to the 'curr_index' of the row
if (mat1[i][curr_index1[i]-1] != value1)
present1 = false;
// Now if all elements of the row have
// been traversed
if (curr_index1[i] == m){
f = 1;
break;
}
}
// Now if the 'value' is common to all the rows
if (present1)
cout << value1 << " ";
// Now if any row have been completely traversed
// then no more common elements can be found
if (f == 1)
break;
}
}
// Driver program to test above
int main(){
int mat1[][MAX1] = { {13, 2, 15, 4, 17},{15, 3, 2, 4, 36},{15, 2, 15, 4, 12},
{15, 26, 4, 3, 2},{2, 19, 4, 22, 15}};
int m = 5;
findAndPrintCommonElements1(mat1, m);
return 0;
}輸出
2 4 15
更新於： 2020-07-24
214 次瀏覽
廣告