Имеется n человек, которые разбиты на некоторое неизвестное количество групп. Каждому человеку присвоен уникальный идентификатор от 0 до n — 1.
Вам дан целочисленный массив groupSizes, где groupSizes[i] — это размер группы, в которой находится человек i. Например, если groupSizes[1] = 3, то человек 1 должен находиться в группе размера 3.
Возвращает список групп, в котором каждый человекiнаходится в группе размеромgroupSizes[i].
Код C++
класс Решение {
публика:
вектор‹вектор‹int›› groupThePeople(vector‹int›& groupSizes) {
вектор‹вектор‹int>> ans;
unordered_map‹int, вектор‹int›groupSizeToIndices;
for (int i = 0; i ‹ groupSizes.size(); ++i)
groupSizeToIndices[groupSizes[i]].push_back(i);
for (const auto& [groupSize, indexes]: groupSizeToIndices) {
вектор‹int› groupIndices;
for (const int index: indexes) {
groupIndices.push_back(индекс);
if (groupIndices.size() == groupSize) {
ans.push_back(groupIndices);
groupIndices.clear();
}
}
}
вернуть ответ;
}
};
Объяснение:
В коде определяется класс Solution C++ с функцией-членом groupThePeople. Эта функция принимает вектор groupSizes в качестве входных данных и стремится группировать людей в зависимости от размеров их групп. Он возвращает вектор векторов, содержащий сгруппированные индексы.
Вот разбивка кода:
Он начинается с объявления вектора an для хранения конечного результата и unordered_map с именем groupSizeToIndices для сопоставления размеров групп с индексами людей с этим размером группы.
Он перебирает вектор groupSizes и заполняет карту groupSizeToIndices. Для каждого человека он добавляет его индекс к соответствующему ключу размера группы на карте.
Затем он выполняет итерацию по карте groupSizeToIndices. Для каждого размера группы и связанных с ним индексов он создает вектор с именем groupIndices для хранения индексов людей в текущей группе.
В цикле для каждого размера группы он перебирает индексы и добавляет их к вектору groupIndices. Когда вектор groupIndices достигает размера, заданного размером группы, это означает, что группа завершена, поэтому он добавляет вектор groupIndices к конечному результату и очищает вектор groupIndices, чтобы начать формирование следующей группы.
Наконец, он возвращает вектор ответа, содержащий сгруппированные индексы.
Временная сложность:
Временную сложность этого кода можно разбить на следующие компоненты:
Заполнение карты groupSizeToIndices. Это включает однократную итерацию вектора groupSizes и вставку значений в карту. Временная сложность этой операции равна O(n), где n — количество элементов в векторе groupSizes.
Формирование групп и добавление их в ответ. Эта часть включает в себя перебор карты groupSizeToIndices, а затем перебор индексов, связанных с каждым размером группы. Количество итераций формирования групп зависит от общего количества людей, равного n. Следовательно, общая временная сложность этой части равна O(n).
Доминирующим фактором временной сложности является операция формирования групп O(n), поэтому общая временная сложность функции groupThePeople равна O(n).
Таким образом, этот код эффективно группирует людей на основе размеров их групп с временной сложностью O (n), где «n» — количество людей во входном векторе groupSizes.
