Сложность: medium
Есть n человек, которые разделены на неизвестное количество групп. Каждый человек имеет уникальный ID от 0 до n - 1.
Вам дан целочисленный массив groupSizes, где groupSizes[i] - это размер группы, в которой находится человек i. Например, если groupSizes[1] = 3, то человек 1 должен быть в группе размером 3.
Верните список групп таким образом, чтобы каждый человек i находился в группе размером groupSizes[i].
Каждый человек должен быть ровно в одной группе, и каждый человек должен быть в группе. Если существует несколько ответов, верните любой из них. Гарантируется, что для данного ввода существует хотя бы одно правильное решение.
Пример:
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].
👨💻 Алгоритм:
1⃣Инициализируйте пустой список списков ans для хранения индексов групп. Создайте хэш-таблицу szToGroup, где ключи — целые числа, представляющие размеры групп, а значения — массивы соответствующих индексов в группе.
2⃣Итерируйте по массиву groupSizes, для каждого индекса i:
Вставьте индекс i в список szToGroup[groupSizes[i]].
Если размер списка становится равным groupSizes[i], добавьте его в ans и очистите массив для ключа groupSizes[i] в хэш-таблице szToGroup.
3⃣Верните ans.
😎 Решение:
class Solution {
func groupThePeople(_ groupSizes: [Int]) -> [[Int]] {
var ans = [[Int]]()
var szToGroup = [Int: [Int]]()
for i in 0..<groupSizes.count {
let size = groupSizes[i]
if szToGroup[size] == nil {
szToGroup[size] = [Int]()
}
szToGroup[size]!.append(i)
if szToGroup[size]!.count == size {
ans.append(szToGroup[size]!)
szToGroup[size] = [Int]()
}
}
return ans
}
}Ставь 👍 и забирай 📚 Базу знаний