Я пытался решить эту проблему в конкурсе (сейчас завершено) на LeetCode.
В группе из N человек (помечены 0, 1, 2, …, N-1), каждый человек имеет
разные суммы денег и разные уровни тишины.Для удобства мы назовем человека с меткой х, просто «человек
Икс».Мы скажем, что богаче [i] = [x, y], если у человека x определенно больше
деньги, чем человек у. Обратите внимание, что богаче может быть только подмножество действительных
наблюдения.Кроме того, мы скажем спокойно [x] = q, если у человека x есть тишина q.
Теперь верните ответ, где answer [x] = y, если y наименее тихий человек
(то есть человек y с наименьшим значением спокойной [y]), среди всех
люди, которые определенно имеют равные или больше денег, чем человек х.Пример 1:
Ввод: богаче = [[1,0], [2,1], [3,1], [3,7], [4,3], [5,3], [6,3]], quiet =
[3,2,5,4,6,1,7,0] Вывод: [5,5,2,5,4,5,6,7] Объяснение: ответ [0] =
5. Человек 5 имеет больше денег, чем 3, который имеет больше денег, чем 1, который имеет больше денег, чем 0. Единственный, кто тише (имеет меньше
quiet [x]) человек 7, но не ясно, есть ли у них больше денег, чем
человек 0.ответ [7] = 7. Среди всех людей, которые определенно имеют равные или более
деньги, чем человек 7 (которые могут быть людьми 3, 4, 5, 6 или 7),
человек, который является самым тихим (имеет более низкий уровень шума [x]), является человеком 7.Другие ответы могут быть заполнены с аналогичными рассуждениями.
На входе нет циклов.
Это похоже на прямую проблему DFS, где мы отслеживаем quietness
узлов в пути.
И мое решение заключается в следующем
class Solution {
public:
int doDFS(unordered_map<int, bool>& visited,
unordered_map<int, vector<int> > graph, vector<int>& quiet,
vector<int>& answer, int current) {
if (visited.find(current) != visited.end()) {
return answer[current];
}
int current_min = current;
for (int i = 0; i < graph[current].size(); ++i) {
int min_y = doDFS(visited, graph, quiet, answer, graph[current][i]);
if (quiet[current_min] > quiet[min_y]) {
current_min = min_y;
}
}
answer[current] = current_min;
visited[current] = true;
return answer[current];
}
vector<int> loudAndRich(vector<vector<int> >& richer, vector<int>& quiet) {
// vector<vector<int>> graph(quiet.size(), vector<int>());
unordered_map<int, vector<int> > graph;
vector<int> answer(quiet.size());
unordered_map<int, bool> visited;
for (int i = 0; i < richer.size(); ++i) {
// cout << richer[i][1] << ' ' << richer[i][0] << endl;
if (graph.find(richer[i][1]) == graph.end()) {
graph.insert({richer[i][1], vector<int>{richer[i][0]}});
} else {
graph[richer[i][1]].push_back(richer[i][0]);
}
}
for (int i = 0; i < quiet.size(); ++i) {
if (visited.find(i) == visited.end()) {
doDFS(visited, graph, quiet, answer, i);
}
}
return answer;
}
};
Но я не могу принять это, оно истекло для большего ввода.
Время выполнения этого решения O(N)
поскольку мы посещаем каждый узел только один раз.
Может ли кто-нибудь помочь мне понять, почему это истекло?
+ Изменить unordered_map<int, vector<int> > graph
в unordered_map<int, vector<int> > &graph
вы делаете копию на каждый звонок, который дает вам. С этим изменением оно принимается.
Других решений пока нет …