Чемпионат по шагам

Условие задачи

Необходимо определить userids участников, которые прошли наибольшее количество шагов steps за все дни, не пропустив ни одного дня соревнований.

Пример 1

Ввод:

statistics = [
    [{userid: 1, steps: 1000}, {userid: 2, steps: 1500}]
    [{userid: 2, steps: 1000}]
]

Вывод:

champions = {userids: [2], steps: 2500}

Пример 2

Ввод:

statistics = [
    [{userid: 1, steps: 2000}, {userid: 2, steps: 1500}]
    [{userid: 2, steps: 4000}, {userid: 1, steps: 3500}]
]

Вывод:

champions = {userids: [1, 2], steps: 5500}

Решение задачи

Для решения этой задачи нам нужно:

1. Подсчитать общее количество шагов для каждого участника
2. Определить, кто из участников участвовал во все дни соревнований
3. Среди участников, которые участвовали во все дни, найти тех, кто прошел наибольшее количество шагов

Структуры данных

Сначала определим структуры данных для нашей задачи:

type Statistics struct {
    UserID int
    Steps  int
}

type Result struct {
    UserIDs []int
    Steps   int
}

Алгоритм решения

Вот пошаговый алгоритм решения задачи:

Реализация

Вот полная реализация функции getChampions:

func getChampions(statistics [][]Statistics) Result {
    var result Result
    userSteps := make(map[int]int)
    userDays := make(map[int]int)
    
    // Если нет данных, возвращаем пустой результат
    if len(statistics) == 0 {
        return result
    }
    
    // Подсчитываем шаги и дни участия для каждого участника
    for day := range statistics {
        for _, user := range statistics[day] {
            userSteps[user.UserID] += user.Steps
            userDays[user.UserID] += 1
        }
    }
    
    // Находим участников, которые участвовали во всех днях
    for user, steps := range userSteps {
        // Проверяем, участвовал ли пользователь во всех днях
        if userDays[user] == len(statistics) {
            // Если это первый участник или у него больше шагов, чем у текущих лидеров
            if len(result.UserIDs) == 0 || steps > result.Steps {
                result.Steps = steps
                result.UserIDs = []int{user}
            } else if steps == result.Steps {
                // Если у участника столько же шагов, добавляем его к лидерам
                result.UserIDs = append(result.UserIDs, user)
            }
        }
    }
    
    // Сортируем ID участников для стабильного результата
    sort.Ints(result.UserIDs)
    
    return result
}

Тестирование

Давайте проверим нашу функцию на нескольких тестовых случаях:

func main() {
    // Тест на пустой ввод
    fmt.Println("empty", reflect.DeepEqual(getChampions(nil),
        Result{},
    ))
    
    // Тест 1: Один участник участвовал во все дни
    fmt.Println("case 1", reflect.DeepEqual(
        getChampions([][]Statistics{
            {{UserID: 1, Steps: 2000}, {UserID: 2, Steps: 1500}},
            {{UserID: 2, Steps: 1000}},
        }),
        Result{UserIDs: []int{2}, Steps: 2500},
    ))
    
    // Тест 2: Один участник участвовал во все дни, но есть участник с большим количеством шагов
    fmt.Println("case 2", reflect.DeepEqual(
        getChampions([][]Statistics{
            {{UserID: 1, Steps: 2000}, {UserID: 2, Steps: 1500}},
            {{UserID: 2, Steps: 1000}, {UserID: 3, Steps: 4000}},
        }),
        Result{UserIDs: []int{2}, Steps: 2500},
    ))
    
    // Тест 3: Два участника участвовали во все дни, но один прошел больше шагов
    fmt.Println("case 3", reflect.DeepEqual(
        getChampions([][]Statistics{
            {{UserID: 1, Steps: 2000}, {UserID: 2, Steps: 1500}},
            {{UserID: 2, Steps: 1000}, {UserID: 1, Steps: 3000}},
        }),
        Result{UserIDs: []int{1}, Steps: 5000},
    ))
    
    // Тест 4: Несколько участников с одинаковым количеством шагов
    case4answer := getChampions([][]Statistics{
        {{UserID: 1, Steps: 1000}, {UserID: 2, Steps: 1500}, {UserID: 3, Steps: 1500}},
        {{UserID: 2, Steps: 1000}, {UserID: 1, Steps: 1000}, {UserID: 3, Steps: 1000}},
    })
    fmt.Println("case 4", reflect.DeepEqual(
        case4answer,
        Result{UserIDs: []int{2, 3}, Steps: 2500},
    ))
    
    // Тест 5: Никто не участвовал во все дни
    fmt.Println("case 5", reflect.DeepEqual(
        getChampions([][]Statistics{
            {{UserID: 1, Steps: 2000}, {UserID: 2, Steps: 1500}},
            {{UserID: 2, Steps: 1000}},
            {{UserID: 3, Steps: 1000}},
        }),
        Result{},
    ))
    
    // Примеры из условия задачи
    fmt.Println("example 1", reflect.DeepEqual(
        getChampions(
            [][]Statistics{
                {{UserID: 1, Steps: 2000}, {UserID: 2, Steps: 1500}},
                {{UserID: 2, Steps: 1000}},
            }),
        Result{UserIDs: []int{2}, Steps: 2500},
    ))
    fmt.Println("example 2", reflect.DeepEqual(
        getChampions([][]Statistics{
            {{UserID: 1, Steps: 2000}, {UserID: 2, Steps: 1500}},
            {{UserID: 2, Steps: 4000}, {UserID: 1, Steps: 3500}},
        }),
        Result{UserIDs: []int{1, 2}, Steps: 5500},
    ))
}

Анализ решения

Временная сложность

Временная сложность нашего решения составляет O(n), где n - общее количество записей статистики (сумма количества участников по всем дням).

• Проход по всем дням и участникам: O(n)
• Проход по всем уникальным участникам: O(k), где k - количество уникальных участников (k ≤ n)
• Сортировка ID участников: O(m log m), где m - количество чемпионов (обычно m << n)

Итоговая сложность: O(n + k + m log m) ≈ O(n), так как k ≤ n и обычно m << n.

Пространственная сложность

Пространственная сложность составляет O(k), где k - количество уникальных участников:

• Карта userSteps: O(k)
• Карта userDays: O(k)
• Результат: O(m), где m - количество чемпионов (обычно m << k)

Итоговая пространственная сложность: O(k + m) ≈ O(k).

Заключение

Мы решили задачу о чемпионате по шагам, используя хеш-таблицы для эффективного подсчета шагов и дней участия каждого участника. Наше решение имеет линейную временную сложность и эффективно работает даже с большими наборами данных.

Ключевые моменты решения:

• Использование хеш-таблиц для быстрого доступа и обновления данных
• Проверка участия во всех днях соревнований
• Поиск участников с максимальным количеством шагов
• Сортировка результатов для стабильного вывода