मान लीजिए हमारे पास भिन्नों की एक सूची है जहां प्रत्येक भिन्न में [अंश, हर] (अंश / हर) होता है। हमें भिन्नों की एक नई सूची ज्ञात करनी है जैसे कि भिन्नों में संख्याएँ:
- अपने सबसे सरल रूप में हों (20/14, 10/7 बन जाता है)।
- कोई भी डुप्लिकेट भिन्न (सरल करने के बाद) हटा दिए जाएं।
- उनके वास्तविक मान के अनुसार आरोही क्रम में सॉर्ट किए जाएं।
- यदि संख्या ऋणात्मक है, तो '-' चिह्न अंश के साथ होगा।
उदाहरण के लिए, यदि इनपुट है {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}}, तो आउटपुट [[-1, 2], [2, 1], [7, 3], [5, 1]] होगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- एक सेट
sपरिभाषित करें। n := v का आकार- एक सरणी
rबनाएं। i := 0सेn-1तक लूप चलाएं:c := |v[i][0]| और |v[i][1]| का GCDv[i][0] := v[i][0] / cv[i][1] := v[i][1] / c{v[i][0], v[i][1]}कोrके अंत में डालें।
rसरणी को उनके मानों के आधार पर सॉर्ट करें।- एक सरणी
retबनाएं। i := 0सेr के आकार - 1तक लूप चलाएं:- यदि
retखाली नहीं है औरretका अंतिम तत्वr[i]के समान है, तो जारी रखें। - अन्यथा
r[i]कोretके अंत में डालें।
- यदि
retलौटाएं।
C++ कार्यान्वयन
#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));
return 0;
}
इनपुट
{{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}}
आउटपुट
[[-1, 2, ],[2, 1, ],[7, 3, ],[5, 1, ],]