บุคคลที่รายชื่อบริษัทโปรดไม่ใช่กลุ่มย่อยของรายการอื่นใน C++

สมมติว่าเรามีอาร์เรย์ที่เรียกว่าบริษัทที่ชื่นชอบ โดยที่ FavoriteCompanies[i] คือรายชื่อบริษัทในรายการโปรดของบุคคล ith เราต้องหาดัชนีของบุคคลที่มีรายชื่อบริษัทโปรดไม่ใช่กลุ่มย่อยของบริษัทในรายการโปรดอื่นๆ

ดังนั้น ถ้าอินพุตเป็นเหมือน FavoriteCompanies =[["TCS", "google", "facebook"], ["google","microsoft"], ["google", "facebook"], ["google"], ["amazon"]] จากนั้นผลลัพธ์จะเป็น [0,1,4] เนื่องจากบุคคลที่มี index=2 มี ["google", "facebook"] ซึ่งเป็นชุดย่อยของ FavoriteCompanies[0]=[" TCS", "google", "facebook"] ตรงกับบุคคลที่มีดัชนี 0

ตอนนี้ บุคคลที่มี index=3 มี ["google"] ซึ่งเป็นชุดย่อยของ FavoriteCompanies[0]=["TCS", "google", "facebook"] และ favoriteCompanies[1]=["google", "microsoft"] . รายชื่อบริษัทโปรดอื่นๆ ไม่ได้เป็นส่วนหนึ่งของรายการอื่น ดังนั้น คำตอบคือ [0,1,4]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน ok() ซึ่งจะใช้อาร์เรย์ a อาร์เรย์ b

• cnt :=0, ผม :=0, j :=0

• ในขณะที่ (i <ขนาดของ a และ j <ขนาดของ b) ทำ −

  • ถ้า a[i] เหมือนกับ b[j] แล้ว −

    • (เพิ่ม i, j และ cnt โดย 1)

  • มิฉะนั้นเมื่อ a[i]

    • (เพิ่ม i ขึ้น 1)

  • มิฉะนั้น

    • (เพิ่มขึ้น j โดย 1)

• คืนค่า true เมื่อ cnt

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดหนึ่งชุด s

• n :=ขนาด f

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • จัดเรียงอาร์เรย์ f[i]

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ค :=จริง

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้าฉันเหมือนกับ j แล้ว −

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • c :=c และ 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","facebo
ok"},{"google"},{"amazon"}};
print_vector(ob.peopleIndexes(v));
}

อินพุต

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

ผลลัพธ์

[0, 1, 4, ]