資料結構
網路
關係資料庫管理系統 (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
