Найти пользователей с наибольшей суммой шагов, не пропустивших ни дня
Соревнование по шагам идёт несколько дней. statistics[d] содержит записи {userID, steps} за день d. Верните ID пользователей с наибольшей суммой шагов среди только тех, кто участвовал каждый день, и эту сумму.
Ограничения:
- Пользователь, пропустивший любой день, не учитывается, какой бы ни была сумма.
- Победителей может быть несколько (ничья) или ни одного (пустой вход → пустой результат).
- Стремитесь к одному проходу; без вложенного поиска вхождения и без сортировки.
type Entry struct {
UserID int
Steps int
}
type Result struct {
UserIDs []int
Steps int
}
func champions(statistics [][]Entry) Result {
// ваш код здесь
}Допишите реализацию.
Заполните map userID → {daysIn, stepsSum} только по дню 0 — кто не был в день 0, не может быть в каждом дне. Для каждого следующего дня инкрементируйте daysIn и stepsSum только тем, кто уже в map. Затем по map оставьте тех, у кого daysIn == len(statistics), найдите среди них максимум stepsSum и соберите всех с этим максимумом. Пустой вход даёт пустой Result.
- ✗Добавлять новых пользователей из поздних дней, которых не было в каждом дне
- ✗Использовать вложенный поиск вхождения вместо одного прохода-накопления
- ✗Возвращать одного победителя вместо сбора всех с максимумом
- →Почему заполнение по дню 0 — ключ к отказу от поиска вхождения?
- →Какова временная сложность относительно общего числа записей?
Решение
func champions(statistics [][]Entry) Result {
if len(statistics) == 0 {
return Result{}
}
type acc struct {
daysIn int
stepsSum int
}
candidates := make(map[int]*acc)
// День 0 задаёт пул кандидатов: новых позже не добавляем.
for _, e := range statistics[0] {
candidates[e.UserID] = &acc{daysIn: 1, stepsSum: e.Steps}
}
// Следующие дни: инкремент только уже известных.
for d := 1; d < len(statistics); d++ {
for _, e := range statistics[d] {
if a, ok := candidates[e.UserID]; ok {
a.daysIn++
a.stepsSum += e.Steps
}
}
}
total := len(statistics)
maxSteps := -1
for _, a := range candidates {
if a.daysIn == total && a.stepsSum > maxSteps {
maxSteps = a.stepsSum
}
}
if maxSteps < 0 {
return Result{}
}
var winners []int
for id, a := range candidates {
if a.daysIn == total && a.stepsSum == maxSteps {
winners = append(winners, id)
}
}
return Result{UserIDs: winners, Steps: maxSteps}
}Сложность. Один проход по всем записям — O(N), где N — суммарное число записей; память O(K) под кандидатов первого дня. Никакого вложенного поиска вхождения и сортировки.
Ключевая идея. Победитель обязан быть в каждом дне, значит и в дне 0. Заполнив map по дню 0, новых добавлять не нужно — это и убирает квадратичную проверку «был ли пользователь в этот день».
