C++ . में अद्वितीय भिन्न

मान लीजिए कि हमारे पास भिन्नों की एक सूची है जहाँ प्रत्येक भिन्न में [अंश, हर] (अंश / हर) होता है। हमें भिन्नों की एक नई सूची इस प्रकार मिली है कि भिन्नों में संख्याएं हैं -

• उनकी सबसे कम शर्तों में। (20/14 10/7 हो जाता है)।

• कोई भी डुप्लीकेट अंश (घटाने के बाद) हटा दिए जाएंगे।

• आरोही क्रम में उनके वास्तविक मान के अनुसार क्रमबद्ध।

• यदि संख्या ऋणात्मक है, तो '-' चिह्न अंश के साथ होगा।

इसलिए, यदि इनपुट {{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}} जैसा है, तो आउटपुट होगा हो [[-1, 2],[2, 1],[7, 3],[5, 1]]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक सेट को परिभाषित करें

• n:=वी का आकार

• एक सरणी बनाएं r

• इनिशियलाइज़ i :=0 के लिए, जब i

  • सी:=जीसीडी |v[i, 0]| और |v[i, 1]|

  • v[i, 0] :=v[i, 0] / c

  • v[i, 1] :=v[i, 1] / c

  • r के अंत में {v[i, 0], v[i, 1]} डालें

• सरणी r को उनके मूल्यों के आधार पर क्रमबद्ध करें

• एक सरणी बनाएं रिट

• इनिशियलाइज़ i :=0 के लिए, जब i

  • यदि रिट खाली नहीं है और रिट का अंतिम तत्व r[i] के समान है, तो -

    • रिट के अंत में r[i] डालें

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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));
}

इनपुट

{{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}}

आउटपुट

[[-1, 2, ],[2, 1, ],[7, 3, ],[5, 1, ],]