d550 - 物件排序
題目描述
題目要求讀取一個 N x M 的矩陣，並按照行優先的順序進行排序。排序的規則是先比較第一列，如果相同則比較第二列，以此類推，直到比較完所有列。
解題思路
題目要求對一個二維陣列進行排序，排序的依據是逐列比較。最直接的方法是使用 C++ 的 std::sort 函數，並配合 vector 儲存二維陣列。std::sort 預設會使用小於運算符 < 進行比較，因此可以直接對 vector<vector<long long int>> 進行排序，它會自動按照行優先的順序進行比較。
複雜度分析
- 時間複雜度: O(N * M * log N)，其中 N 是行數，M 是列數。
std::sort的時間複雜度是 O(N * log N)，而每次比較兩個行需要 O(M) 的時間。 - 空間複雜度: O(N * M)，用於儲存輸入的二維陣列。
程式碼
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main (){
//ios::sync_with_stdio(0);cin.tie(0);
long long int a,b,tem;
while(cin >> a >> b){
vector<vector<long long int> > c;//高=a,寬=b
vector<long long int> d;
c.resize(a);
d.resize(b);
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
scanf("%lld",&d[j]);
}
c[i]=d;
}
printf("\n");
//------------------------------
/* for(int i=0;i<a;i++){
for(int j=a-(a-i)+1;j<a;j++){
for(int l=0;l<b;l++){
if(c[i][l]>c[j][l]){
for(int k=0;k<b;k++){
tem=c[i][k];
c[i][k]=c[j][k];
c[j][k]=tem;
}
}
}
}
}*/
sort(c.begin(),c.end());
//------------------------------
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
printf("%lld ",c[i][j]);
}
printf("\n");
}
}
}