©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>先来看一个每日一题
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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中调用非静态成员函数。
静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。