План курса / Все задачи / Алгоритмы и структуры данных
Соревнования по числу шaгов
средне
# решено
Недавно закончился чемпионат по шагам и тебе нужно подвести его итоги! Дан массив statistics, где statistics[i] = [[id участника, число шагов в i-ый день], ...]. Нужно вернуть id всех участников, которые прошли максимальное число шагов и одновременно с этом принимали участие в соревнованиях каждый день. Результат можно вернуть в любом порядке.
Если ни один из участников не принимал участие в соревнованиях каждый день, то нужно вернуть пустой массив.
Пример 1:
Ввод: statistics =
[[[1,1000],[2,3500]]
,[[1,1500]]]
Вывод: [1]
Объяснение: только участник с id=1 участвовал в соревнованиях каждый день.
Пример 2:
Ввод: statistics =
[[[2,4000],[9,500],[4,2000],[6,1000]]
,[[9,5000],[2,1500],[4,5500],[6,2000]]
,[[2,3420],[9,10000],[6,10850],[4,8000]]]
Вывод: [9,4]
Объяснение: все участники принимали участие каждый день, но участники с id=9 и id=4 прошли больше всего шагов.
Ограничения:
len(statistics) >= 1
public class Solution
{
public static List<int> FindCompetitionWinners(List<List<List<int>>> statistics)
{
Dictionary<int, int[]> userStats = new Dictionary<int, int[]>(); // {user_id: {days_count, steps_count}}
int maxStepsCount = 0; // максимальное число шагов среди участников, которые участвовали каждый день
foreach (var day in statistics)
{
foreach (var user in day)
{
int userId = user[0];
int userStepsCount = user[1];
if (!userStats.ContainsKey(userId))
{
userStats[userId] = new int[2]; // инициализируем дни и шаги
}
// увеличиваем кол-во дней и число шагов для userId
userStats[userId][0]++;
userStats[userId][1] += userStepsCount;
// обновляем maxStepsCount, если было участие во всех днях
if (userStats[userId][0] == statistics.Count)
{
maxStepsCount = Math.Max(maxStepsCount, userStats[userId][1]);
}
}
}
// формируем результирующий список из id участников
List<int> result = new List<int>();
foreach (var kvp in userStats)
{
if (kvp.Value[0] == statistics.Count && kvp.Value[1] == maxStepsCount)
{
result.Add(kvp.Key);
}
}
return result;
}
}
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> findCompetitionWinners(const vector<vector<vector<int>>>& statistics) {
unordered_map<int, pair<int, int>> userStats; // {user_id: {days_count, steps_count}}
int maxStepsCount = 0; // максимальное число шагов среди участников, которые участвовали каждый день
for (const auto& day : statistics) {
for (const auto& user : day) {
int userId = user[0];
int userStepsCount = user[1];
if (userStats.find(userId) == userStats.end()) {
userStats[userId] = {0, 0}; // инициализируем дни и шаги
}
// увеличиваем кол-во дней и число шагов для userId
userStats[userId].first += 1;
userStats[userId].second += userStepsCount;
// обновляем maxStepsCount, если было участие во всех днях
if (userStats[userId].first == statistics.size()) {
maxStepsCount = max(maxStepsCount, userStats[userId].second);
}
}
}
// формируем результирующий массив из id участников
vector<int> result;
for (const auto& entry : userStats) {
int userId = entry.first;
const auto& stat = entry.second;
if (stat.first == statistics.size() && stat.second == maxStepsCount) {
result.push_back(userId);
}
}
return result;
}
package main
import (
"math"
)
func findCompetitionWinners(statistics [][][]int) []int {
userStats := make(map[int][]int) // {user_id: {days_count, steps_count}}
maxStepsCount := 0 // максимальное число шагов среди участников, которые участвовали каждый день
for _, day := range statistics {
for _, user := range day {
userId, userStepsCount := user[0], user[1]
if _, exists := userStats[userId]; !exists {
userStats[userId] = []int{0, 0} // инициализируем дни и шаги
}
// увеличиваем кол-во дней и число шагов для userId
userStats[userId][0]++
userStats[userId][1] += userStepsCount
// обновляем maxStepsCount, если было участие во всех днях
if userStats[userId][0] == len(statistics) {
maxStepsCount = int(math.Max(float64(maxStepsCount), float64(userStats[userId][1])))
}
}
}
// формируем результирующий массив из id участников
result := []int{}
for userId, stat := range userStats {
if stat[0] == len(statistics) && stat[1] == maxStepsCount {
result = append(result, userId)
}
}
return result
}
import java.util.*;
public class Solution {
public List<Integer> findCompetitionWinners(List<List<List<Integer>>> statistics) {
Map<Integer, int[]> userStats = new HashMap<>();
int maxStepsCount = 0;
for (List<List<Integer>> day : statistics) {
for (List<Integer> user : day) {
int userId = user.get(0);
int userStepsCount = user.get(1);
if (!userStats.containsKey(userId)) {
userStats.put(userId, new int[]{0, 0});
}
userStats.get(userId)[0]++;
userStats.get(userId)[1] += userStepsCount;
if (userStats.get(userId)[0] == statistics.size()) {
maxStepsCount = Math.max(maxStepsCount, userStats.get(userId)[1]);
}
}
}
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, int[]> entry : userStats.entrySet()) {
int userId = entry.getKey();
int[] stat = entry.getValue();
if (stat[0] == statistics.size() && stat[1] == maxStepsCount) {
result.add(userId);
}
}
return result;
}
}
from typing import *
def find_competition_winners(statistics: List[List[List[int]]]) -> List[int]:
user_stats = {}
# max_steps_count: максимальное число шагов среди участников, которые
# участвовали каждый день
max_steps_count = 0
for day in statistics:
for user in day:
user_id, user_steps_count = user
if user_id not in user_stats:
user_stats[user_id] = [0, 0]
# увеличиваем кол-во дней и число шагов для user_id
days_count = user_stats[user_id][0] + 1
steps_count = user_steps_count + user_stats[user_id][1]
user_stats[user_id] = [days_count, steps_count]
# обновляем max_steps_count, если было участие во всех днях
if days_count == len(statistics):
max_steps_count = max(max_steps_count, steps_count)
# формируем результирующий массив из id участников
result = []
for user_id in user_stats:
user_stat = user_stats[user_id]
if user_stat[0] == len(statistics) and user_stat[1] == max_steps_count:
result.append(user_id)
return result
export function findCompetitionWinners(statistics) {
let userStats = {};
// maxStepsCount: максимальное число шагов среди участников, которые
// участвовали каждый день
let maxStepsCount = 0;
for (let day of statistics) {
for (let user of day) {
let [userId, userStepsCount] = user;
if (!(userId in userStats)) {
userStats[userId] = [0, 0];
}
// увеличиваем кол-во дней и число шагов для userId
let daysCount = userStats[userId][0] + 1;
let stepsCount = userStepsCount + userStats[userId][1];
userStats[userId] = [daysCount, stepsCount];
// обновляем maxStepsCount, если было участие во всех днях
if (daysCount === statistics.length) {
maxStepsCount = Math.max(maxStepsCount, stepsCount);
}
}
}
// формируем результирующий массив из id участников
let result = [];
for (let userId in userStats) {
let userStat = userStats[userId];
if (userStat[0] === statistics.length && userStat[1] === maxStepsCount) {
result.push(parseInt(userId));
}
}
return result;
}
Оценка сложности
Время: O(n), где n - число записей о всех пользователях.
Память: O(n), где n - число записей о всех пользователях.