最喜欢的公司列表不是C ++中另一个列表的子集的人
假设我们有一个名为“最喜欢的公司”的数组,其中“favouriteCompanies[i]”是第i个人的最喜欢的公司的列表。我们必须找到其喜爱的公司列表不是喜爱的其他公司列表的子集的人员的索引。
因此,如果输入就像“favouriteCompanies==[[“TCS”,“google”,“facebook”],[“google”,“microsoft”],[“google”,“facebook”],[“google”],[“amazon”]],那么输出将为[0,1,4],这是因为索引为2的人具有[“google”,“facebook”],这是favoriteCompanies[0]=[“TCS”,“google”,“facebook”]对应于索引为0的人。
现在索引为3的人具有[“google”],它是[favouriteCompanies[0]=[“TCS”,“google”,“facebook”]和收藏夹[1]=[“google”,“microsoft”]的子集。其他喜欢的公司列表不是另一个列表的子集,因此答案是[0,1,4]。
为了解决这个问题,我们将遵循以下步骤-
定义一个函数ok()
,它将使用一个数组a,一个数组b,
cnt:=0,i:=0,j:=0
而(i<a的大小和j<b的大小),做-
(将j增加1)
(将i增加1)
(将i,j和cnt增加1)
如果a[i]与b[j]相同,则-
否则,当a[i]<b[j]时,则-
除此以外
当cnt<a的大小时返回true
从主要方法中执行以下操作-
定义一组
n:=f的大小
对于初始化i:=0,当i<n时,更新(将i增加1),执行-
对数组f[i]排序
对于初始化i:=0,当i<n时,更新(将i增加1),执行-
将我插入s
如果i与j相同,则-
c:=cANDok(f[i],f[j])
忽略以下部分,跳至下一个迭代
c:=真
对于初始化j:=0,当j<n时,更新(将j增加1),执行-
如果c不为零,则-
将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, ]