C++ में वे लोग जिनकी पसंदीदा कंपनियों की सूची किसी अन्य सूची का सबसेट नहीं है

मान लीजिए हमारे पास favoriteCompanies नामक एक ऐरे है जहां favoriteCompanies[i] i-वें व्यक्ति की पसंदीदा कंपनियों की सूची है। हमें उन लोगों के इंडेक्स ढूंढने हैं जिनकी पसंदीदा कंपनियों की सूची किसी अन्य व्यक्ति की पसंदीदा कंपनियों की सूची का सबसेट नहीं है।

इसलिए, यदि इनपुट है favoriteCompanies = [["TCS", "google", "facebook"], ["google","microsoft"], ["google", "facebook"], ["google"], ["amazon"]], तो आउटपुट होगा [0,1,4], क्योंकि इंडेक्स=2 वाले व्यक्ति के पास ["google", "facebook"] है जो favoriteCompanies[0]= ["TCS", "google", "facebook"] का सबसेट है जो इंडेक्स 0 वाले व्यक्ति से संबंधित है।

अब इंडेक्स=3 वाले व्यक्ति के पास ["google"] है जो favoriteCompanies[0]= ["TCS", "google", "facebook"] और favoriteCompanies[1]= ["google", "microsoft"] का सबसेट है। अन्य पसंदीदा कंपनियों की सूचियाँ किसी अन्य सूची का सबसेट नहीं हैं, इसलिए उत्तर [0,1,4] है।

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

• एक फ़ंक्शन ok() परिभाषित करें, जो एक ऐरे a, एक ऐरे b लेगा,

• cnt := 0, i := 0, j := 0

• जब (i < a का आकार और j < b का आकार), करें -

  • यदि a[i], b[j] के समान है, तो -

    • (i, j और cnt को 1 से बढ़ाएं)

  • अन्यथा जब a[i] < b[j], तो -

    • (i को 1 से बढ़ाएं)

  • अन्यथा

    • (j को 1 से बढ़ाएं)

• true लौटाएं जब cnt < a का आकार

• मुख्य विधि से निम्न करें -

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

• n := f का आकार

• i := 0 से शुरू करें, जब i < n, i बढ़ाते हुए, करें -

  • f[i] ऐरे को सॉर्ट करें

• i := 0 से शुरू करें, जब i < n, i बढ़ाते हुए, करें -

  • c := true

  • j := 0 से शुरू करें, जब j < n, j बढ़ाते हुए, करें -

    • यदि i, j के समान है, तो -

      • बाकी भाग को अनदेखा करें, अगले इटरेशन पर जाएं

    • c := c AND ok(f[i], f[j])

  • यदि c नॉन-जीरो है, तो -

    • i को s में डालें

• s के एलिमेंट्स को ऐरे के रूप में लौटाएं

उदाहरण

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

#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:    bool ok(vector<string>& a, vector<string>& b){       int cnt = 0;       int i = 0;       int j = 0;       while (i < a.size() && j < b.size()) {          if (a[i] == b[j]) {             i++;             j++;             cnt++;          }          else if (a[i] < b[j]) {             i++;          }          else {             j++;          }       }       return cnt < a.size();    }    vector<int> peopleIndexes(vector<vector<string> >& f){       set<int> s;       int n = f.size();       for (int i = 0; i < n; i++) {          sort(f[i].begin(), f[i].end());       }         for (int i = 0; i < n; i++) {          bool c = true;          for (int j = 0; j < n; j++) {             if (i == j)                continue;             c &= ok(f[i], f[j]);          }          if (c)             s.insert(i);       }       return vector<int>(s.begin(), s.end());    } }; main(){    Solution ob;    vector<vector<string>> v = {{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}; print_vector(ob.peopleIndexes(v)); }

इनपुट

{{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}

आउटपुट

[0, 1, 4, ]