FavoriteCompanies[i]가 i번째 사람의 즐겨찾기 회사 목록인 즐겨찾기 회사라는 배열이 있다고 가정합니다. 선호하는 회사 목록이 다른 선호하는 회사 목록의 하위 집합이 아닌 사람들의 인덱스를 찾아야 합니다.
따라서 입력이 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인 사람은 FavoriteCompanies[0]=["TCS", "google", "facebook"] 및 FavoriteCompanies[1]=["google", "microsoft"]의 하위 집합인 ["google"]을 가집니다. . 좋아하는 회사의 다른 목록은 다른 목록의 하위 집합이 아니므로 답은 [0,1,4]입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ok() 함수를 정의하면 배열 a, 배열 b,
가 사용됩니다. -
cnt :=0, i :=0, j :=0
-
동안 (i <크기 및 j
-
a[i]가 b[j]와 같으면 -
-
(i, j, cnt를 1씩 증가)
-
-
그렇지 않으면 a[i]
-
(i를 1씩 증가)
-
-
그렇지 않으면
-
(j를 1씩 증가)
-
-
-
cnt
인 경우 true를 반환합니다. -
주요 방법에서 다음을 수행하십시오 -
-
한 세트 정의
-
n :=f의 크기
-
initialize i :=0의 경우, i
-
배열 f[i]
정렬
-
-
initialize i :=0의 경우, i
-
c :=참
-
j 초기화의 경우:=0, j
-
i가 j와 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
c :=c AND ok(f[i], f[j])
-
-
c가 0이 아니면 -
-
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, ]