Дети с наибольшим количеством конфет

Легкая

array , easy

19 March 2024

Описание задачи #

Есть n детей с конфетами.

Вам дан целочисленный массив candies, где candies[i] представляет количество конфет, которые есть у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Верните массив result длины n, где result[i] имеет значение true, если после предоставления i-му ребенку всех дополнительных конфет у него будет наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут получить наибольшее количество конфет одновременно.

Ограничения #

Длина массива candies находится в диапазоне от 1 до 100
У каждого ребенка может быть не менее 1 и не более 100 конфет
Значение extraCandies находится в диапазоне от 1 до 50

Примеры #

Входные данные: candies = [2,3,5,1,3], extraCandies = 3

Ответ: [true,true,true,false,true]
Входные данные: candies = [4,2,1,1,2], extraCandies = 1

Ответ: [true,false,false,false,false]
Входные данные: candies = [12,1,12], extraCandies = 10

Ответ: [true,false,true]

Решение #

Для решения задачи мы можем найти максимальное количество конфет среди всех детей и затем проверить, превысит ли количество конфет у конкретного ребенка максимум, если к его количеству конфет добавить extraCandies.

Реализация #

package kids_with_the_greatest_number_of_candies

import "slices"

func kidsWithCandies(candies []int, extraCandies int) []bool {
	res := make([]bool, 0, len(candies))

	maxCandies := slices.Max(candies)

	for _, count := range candies {
		res = append(res, count+extraCandies >= maxCandies)
	}

	return res
}

export const kidsWithCandies = (candies: number[], extraCandies: number): boolean[] => {
    let res: boolean[] = []

    const maxCandies = Math.max(...candies)

    candies.forEach(count => {
        res.push(count + extraCandies >= maxCandies)
    })

    return res
}

Оценка сложности #

По времени

Для того чтобы найти ответ, мы дважды итерируемся по массиву, то есть совершаем 2n операций. Итоговая сложность алгоритма равна O(n).

По памяти

Сложность по памяти линейная O(n), так как мы создаем массив длиной n для хранения ответа.

Оригинал задачи на Leetcode

Algorithmics