Giả sử chúng ta có một danh sách các phân số trong đó mỗi phân số chứa [tử số, mẫu số] (tử số / mẫu số). Chúng tôi đã tìm thấy một danh sách mới các phân số sao cho các số trong phân số là -
-
Trong các điều khoản giảm nhất của họ. (20/14 trở thành 10/7).
-
Mọi phân số trùng lặp (sau khi giảm) sẽ bị loại bỏ.
-
Được sắp xếp theo thứ tự tăng dần theo giá trị thực của chúng.
-
Nếu số âm, dấu '-' sẽ ở cùng tử số.
Vì vậy, nếu đầu vào giống như {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {- 6, 12}}, thì đầu ra sẽ là [[-1, 2], [2, 1], [7, 3], [5, 1]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bộ s
-
n:=kích thước của v
-
tạo một mảng r
-
để khởi tạo i:=0, khi i
-
c:=gcd của | v [i, 0] | và | v [i, 1] |
-
v [i, 0]:=v [i, 0] / c
-
v [i, 1]:=v [i, 1] / c
-
chèn {v [i, 0], v [i, 1]} vào cuối r
-
-
sắp xếp mảng r dựa trên các giá trị của chúng
-
tạo một mảng ret
-
để khởi tạo i:=0, khi tôi
-
nếu ret không trống và phần tử cuối cùng của ret giống với r [i], thì -
-
chèn r [i] vào cuối ret
-
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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; } class Solution { public: static bool cmp(vector <int>& a, vector <int>& b){ double aa = (double)a[0] / (double)a[1]; double bb = (double)b[0] / (double)b[1]; return aa < bb; } vector<vector<int>> solve(vector<vector<int>>& v) { set < vector <int> > s; int n = v.size(); vector < vector <int> > r; for(int i = 0; i < n; i++){ int c = __gcd(abs(v[i][0]), abs(v[i][1])); v[i][0] /= c; v[i][1] /= c; r.push_back({v[i][0], v[i][1]}); } sort(r.begin(), r.end(), cmp); vector < vector <int> > ret; for(int i = 0; i < r.size(); i++){ if(!ret.empty() && ret.back() == r[i]) continue; ret.push_back(r[i]); } return ret; } }; int main(){ vector<vector<int>> v = {{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{- 6, 12}}; Solution ob; print_vector(ob.solve(v)); }
Đầu vào
{{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}}
Đầu ra
[[-1, 2, ],[2, 1, ],[7, 3, ],[5, 1, ],]