Mọi người Danh sách công ty yêu thích của ai không phải là một tập hợp con của một danh sách khác trong C ++

Giả sử chúng ta có một mảng được gọi là các công ty yêu thích trong đó favouriteCompanies [i] là danh sách các công ty yêu thích của người thứ i. Chúng tôi phải tìm chỉ số của những người có danh sách công ty yêu thích không phải là một tập hợp con của bất kỳ danh sách công ty yêu thích nào khác.

Vì vậy, nếu đầu vào giống như favouriteCompanies =[["TCS", "google", "facebook"], ["google", "microsoft"], ["google", "facebook"], ["google"], ["amazon"]], thì đầu ra sẽ là [0,1,4], điều này là do người có index =2 có ["google", "facebook"] là một tập hợp con của favouriteCompanies [0] =[" TCS "," google "," facebook "] tương ứng với người có chỉ số 0.

Giờ đây, người có index =3 có ["google"] là tập hợp con của favouriteCompanies [0] =["TCS", "google", "facebook"] và favouriteCompanies [1] =["google", "microsoft"] . Các danh sách công ty yêu thích khác không phải là một tập hợp con của danh sách khác, vì vậy, câu trả lời là [0,1,4].

Để 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 hàm ok (), điều này sẽ lấy một mảng a, một mảng b,

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

• while (i

  • nếu a [i] giống với b [j] thì -

    • (tăng i, j và cnt lên 1)

  • ngược lại khi a [i]

    • (tăng tôi lên 1)

  • Nếu không

    • (tăng j lên 1)

• trả về true khi cnt

• Từ phương thức chính, thực hiện như sau -

• Xác định một bộ s

• n:=kích thước của f

• để khởi tạo i:=0, khi i

  • sắp xếp mảng f [i]

• để khởi tạo i:=0, khi i

  • c:=true

  • để khởi tạo j:=0, khi j

    • nếu tôi giống với j, thì -

      • Bỏ qua phần sau, chuyển sang lần lặp tiếp theo

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

  • nếu c khác 0 thì -

    • chèn tôi vào s

• trả về các phần tử của s dưới dạng một mảng

#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, ]