Giả sử chúng ta có một danh sách các danh sách được gọi là nums, chúng ta phải hiển thị tất cả các phần tử của nums theo thứ tự đường chéo.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định ret mảng
-
Xác định một mảng 2D v
-
để khởi tạo i:=0, khi tôi
-
để khởi tạo j:=0, khi j
-
chèn {nums [i, j], i, j} vào cuối v
-
-
-
sắp xếp mảng v
-
cho mỗi nó trong v, do,
-
chèn nó [0] vào cuối ret
-
-
trả lại ret
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<int> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: static bool cmp(vector <int>& a, vector <int>& b ){ int sum1 = a[1] + a[2]; int sum2 = b[1] + b[2]; return sum1 == sum2 ? a[1] > b[1] : sum1 < sum2; } vector<int> findDiagonalOrder(vector& nums) { vector<int> ret; vector<vector<int> > v; for (int i = 0; i < nums.size(); i++) { for (int j = 0; j < nums[i].size(); j++) { v.push_back({ nums[i][j], i, j }); } } sort(v.begin(), v.end(), cmp); for (auto& it : v) ret.push_back(it[0]); return ret; } }; main(){ Solution ob; vector<vector<int>> v = {{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}; print_vector(ob.findDiagonalOrder(v)); }
Đầu vào
{{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}
Đầu ra
[1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16, ]