数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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)
如果cnt < a的长度，则返回true
在主方法中执行以下操作：
定义一个集合s
n := f的长度
当i从0开始，i < n时，执行 (i加1)：
对数组f[i]进行排序
当i从0开始，i < n时，执行 (i加1)：
c := true
当j从0开始，j < n时，执行 (j加1)：
如果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","facebo
ok"},{"google"},{"amazon"}};
print_vector(ob.peopleIndexes(v));
}输入
{{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}输出
[0, 1, 4, ]
浏览量：103
