Hãy xem xét chúng ta có một danh sách ngẫu nhiên những người đang đứng trong một hàng đợi. Nếu mỗi người được mô tả bằng một cặp số nguyên (h, k), trong đó h là chiều cao và k là số người phía trước anh ta có chiều cao lớn hơn hoặc bằng h. Chúng ta phải xác định một phương pháp để tạo lại hàng đợi. Vì vậy, nếu mảng đã cho giống như [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]], thì đầu ra sẽ là [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- sắp xếp mảng đã cho dựa trên chiến lược so sánh sau đây
- nếu a [0] =b [0], thì trả về a [1]> b [1], nếu không thì trả về a [0]
- tạo một vectơ được gọi là ans
- cho tôi trong phạm vi kích thước của mảng đã cho xuống 0
- insert (phần tử đầu tiên của ans + p [i, 1], p [i]) vào mảng ans
- trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
bool cmp(vector <int> a, vector <int> b){
if(a[0] == b[0])return a[1] > b[1];
return a[0] < b[0];
}
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
sort(p.begin(), p.end(), cmp);
vector < vector <int> > ans;
for(int i = p.size()-1; i>=0; i--){
ans.insert(ans.begin() + p[i][1], p[i]);
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
print_vector(ob.reconstructQueue(v));
} Đầu vào
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Đầu ra
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]