当前位置：首页 > article >正文

对元素为 pair 的数组的各元素进行排序的方法

article 2024/11/25 22:58:07

【知识点】
● 按结构体某一字段对结构体数组进行排序
https://blog.csdn.net/hnjzsyjyj/article/details/120184972
据此知识点，则可构建 pair 元素数组的自定义排序代码如下所示。

typedef pair<int,int> PII;

int up(PII u,PII v) { //ascending by first
    if(u.first==v.first) return u.second<v.second; //If equal,ascending by second
    return u.first<v.first;
}

int down(PII u,PII v) { //descending by first
    if(u.first==v.first) return u.second>v.second; //If equal,descending by second
    return u.first>v.first;
}

● 对元素为 pair 的数组的各元素进行排序的方法
方法一：构建一个包含 n 个 pair 元素的静态数组 v，然后调用 sort(v,v+n); 排序。此方法默认按 pair 数组元素的 first 域进行非递减排序。若 first 域相同，则按 pair 数组元素的 second 域进行非递减排序。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
typedef pair<int,int> PII;
PII v[maxn];

int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>v[i].first>>v[i].second;
    }
    sort(v,v+n);
    for(int i=0; i<n; i++) {
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
    return 0;
}

/*
in:
5
5 8
3 1
2 9
1 6
5 3

out:
1 6
2 9
3 1
5 3
5 8
*/

针对方法一，若拟按 pair 数组元素的 first 域进行非递增排序，且若 first 域相同，则按 pair 数组元素的 second 域进行非递增排序的代码如下所示。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
typedef pair<int,int> PII;
PII v[maxn];

int up(PII u,PII v) { //ascending by first
    if(u.first==v.first) return u.second<v.second; //If equal,ascending by second
    return u.first<v.first;
}

int down(PII u,PII v) { //descending by first
    if(u.first==v.first) return u.second>v.second; //If equal,descending by second
    return u.first>v.first;
}

int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>v[i].first>>v[i].second;
    }
    sort(v,v+n,down);
    for(int i=0; i<n; i++) {
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
    return 0;
}

/*
in:
5
5 3
1 6
3 1
2 9
5 8

out:
5 8
5 3
3 1
2 9
1 6
*/

方法二：构建一个包含 n 个 pair 元素的动态数组 v，然后调用 sort(v.begin(),v.end()); 排序。此方法默认按 pair 数组元素的 first 域进行非递减排序。若 first 域相同，则按 pair 数组元素的 second 域进行非递减排序。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
typedef pair<int,int> PII;
vector<PII> v;

int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        int x,y;
        cin>>x>>y;
        v.push_back({x,y});
    }
    sort(v.begin(),v.end());
    for(int i=0; i<n; i++) {
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
    return 0;
}

/*
in:
5
5 8
3 1
2 9
1 6
5 3

out:
1 6
2 9
3 1
5 3
5 8
*/

针对方法二，若拟按 pair 数组元素的 first 域进行非递增排序，且若 first 域相同，则按 pair 数组元素的 second 域进行非递增排序的代码如下所示。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
typedef pair<int,int> PII;
vector<PII> v;

int up(PII u,PII v) { //ascending by first
    if(u.first==v.first) return u.second<v.second; //If equal,ascending by second
    return u.first<v.first;
}

int down(PII u,PII v) { //descending by first
    if(u.first==v.first) return u.second>v.second; //If equal,descending by second
    return u.first>v.first;
}

int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        int x,y;
        cin>>x>>y;
        v.push_back({x,y});
    }
    sort(v.begin(),v.end(),down);
    for(int i=0; i<n; i++) {
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
    return 0;
}

/*
in:
5
5 3
1 6
3 1
2 9
5 8

out:
5 8
5 3
3 1
2 9
1 6
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/143719009
https://blog.csdn.net/hnjzsyjyj/article/details/143686676
https://blog.csdn.net/hnjzsyjyj/article/details/143720177
https://blog.csdn.net/qq_40618919/article/details/124388676
https://blog.csdn.net/yzu_120702117/article/details/29249527

查看全文

http://www.kler.cn/a/409214.html