Cho mảng favoriteCompanies với favoriteCompanies[i] là danh sách công ty yêu thích của người i. Tìm chỉ số những người mà danh sách của họ không phải là tập con của bất kỳ danh sách nào khác.
Ví dụ
Đầu vào: [["TCS","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
Đầu ra: [0,1,4] (người 2 là tập con của 0, người 3 là tập con của 0 và 1).
Thuật toán so sánh tập con sau khi sắp xếp
- Sắp xếp từng danh sách công ty theo từ điển.
- Với mỗi người i, kiểm tra xem danh sách của i có phải tập con của j (j ≠ i) nào không:
- Duyệt song song hai mảng đã sắp xếp (hai con trỏ) để đếm phần tử chung.
- Nếu số phần tử chung == kích thước danh sách i → i là tập con của j.
- Nếu i không phải tập con của bất kỳ j nào → thêm vào kết quả.
Triển khai C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
bool isSubset(const vector<string>& a, const vector<string>& b) {
int i = 0, j = 0, cnt = 0;
while (i < a.size() && j < b.size()) {
if (a[i] == b[j]) { ++cnt; ++i; ++j; }
else if (a[i] < b[j]) ++i;
else ++j;
}
return cnt == a.size();
}
public:
vector<int> peopleIndexes(vector<vector<string>>& fav) {
int n = fav.size();
for (auto& v : fav) sort(v.begin(), v.end());
vector res;
for (int i = 0; i < n; ++i) {
bool ok = true;
for (int j = 0; j < n; ++j) if (i != j) {
if (isSubset(fav[i], fav[j])) { ok = false; break; }
}
if (ok) res.push_back(i);
}
return res;
}
};
Độ phức tạp
- Thời gian: O(N^2 * L) với L độ dài trung bình danh sách (sắp xếp O(N L log L) + so sánh O(N^2 L)).
- Không gian: O(1) thêm (sắp xếp in-place).
Kết quả kiểm thử
Đầu vào: {{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}
Đầu ra: [0, 1, 4]