<>先来看一个每日一题

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。
编写一个算法来重建这个队列。

注意:
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int
>>& people) { int n=people.size(); vector<vector<int>>ans; sort(people.begin(),
people.end(),[&](vector<int>&x,vector<int>&y)->bool{return x[0]>y[0]||(x[0]==y[0
]&&x[1]<y[1]);}); vector<int>idx; for(int i=0;i<n;i++){ idx.insert(idx.begin()+
people[i][1],i); } for(int i=0;i<n;i++){ ans.push_back(people[idx[i]]); } return
ans; } };
这个解法很精妙,其中用到了sort自定义排序与lamda,借此回顾一下

<>进入正题

1.sort自定义排序

sort()排序函数是c++头文件include 中的函数,它采用的是一种类似于快排的排序方式,时间复杂度 n*log2(n)。可以对
浮点数,整数,字符,字符串,结构体进行排顺序,排序方法不限于从大到小和从小到大两种,它可以根据使用者的排序规则进行排序**。

2.使用lambda函数
vector<vector<int>> people{ {7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2} }; bool
campare(vector<int> A, vector<int> B) { if (A[0] > B[0]) { return true; } else
if(A[0]==B[0]) { return A[1] < B[1]; } return false; } void print(vector<vector<
int>> people) { for (auto it : people) { cout << it[0] << " " << it[1] << endl;
} } int main() { vector<vector<int>> test = people; //1.默认排序(升序) sort(test.begin
(), test.end()); printf("******默认排序********\n"); print(test); //2.compare排序 test
= people; sort(test.begin(), test.end(), campare); printf(
"******compare排序********\n"); print(test); //3.lambda排序 test = people; sort(test
.begin(), test.end(), [&](vector<int> A, vector<int> B) { if (A[0] > B[0]) {
return true; } else if (A[0] == B[0]) { return A[1] < B[1]; } return false; } );
printf("******lambda排序********\n"); print(test); }
结果:

默认排序**
4 4
5 0
5 2
6 1
7 0
7 1
compare排序**
7 0
7 1
6 1
5 0
5 2
4 4
lambda排序**
7 0
7 1
6 1
5 0
5 2
4 4

注意:(在类的内部定义compare的话)

sort中的比较函数compare要声明为静态成员函数或全局函数,不能作为普通成员函数,否则会报错。 invalid use of non-static
member function
因为:非静态成员函数是依赖于具体对象的,而std::sort这类函数是全局的,因此无法再sort中调用非静态成员函数。

静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问,无须创建任何对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。

技术
今日推荐
PPT
阅读数 82
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信