(Простая задача LeetCode)
Есть n детей с конфетами. Вам дан массив целых чисел candies, где каждое candies[i] представляет количество конфет, которые есть у ith ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.
Возвращает логический массивresultдлиныn, гдеresult[i]равноtrue, если после задания ithраздать всехextraCandies, у них будет наибольшее количество конфет среди всех детей, илиfalseиначе.
Обратите внимание, что несколько детей могут получить наибольшее количество конфет.
Пример 1:
Input: candies = [2,3,5,1,3], extraCandies = 3 Output: [true,true,true,false,true] Explanation: If you give all extraCandies to: - Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids. - Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids. - Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids. - Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids. - Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
Пример 2:
Input: candies = [4,2,1,1,2], extraCandies = 1 Output: [true,false,false,false,false] Explanation: There is only 1 extra candy. Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.
Пример 3:
Input: candies = [12,1,12], extraCandies = 10 Output: [true,false,true]
Ограничения:
n == candies.length2 <= n <= 1001 <= candies[i] <= 1001 <= extraCandies <= 50
Подход
Итак, давайте поймем, каким должен быть наш подход? Любые идеи? Ну, давайте сначала разберемся в вопросе.
Итак, сначала нам дано количество конфет, которое изначально есть у детей, поэтому конфеты = [1,2,3], предположим, что это так.
Теперь найдите максимальное количество конфет в заданном массиве конфет, равное 3. Теперь
конфеты[0]+extraCandies = 1 + 3 = 4 › 3
конфеты[1]+дополнительныеКонфеты = 2 + 3 = 5 ›3
конфеты[2]+дополнительныеКонфеты = 3 + 3 = 6 ›3
Итак, поскольку мы видим, что все дети, получившие эти дополнительные конфеты, будут иметь число, превышающее максимальное количество конфет в данном массиве конфет. И это необходимое решение.
Код выглядит следующим образом:
class Solution {
public:
vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
vector<bool>ans;
int maxm_can = INT_MIN;
for(int i=0;i<candies.size();i++)
{
maxm_can = max(maxm_can,candies[i]);
}
for(int i=0;i<candies.size();i++)
{
if((candies[i]+extraCandies)>=maxm_can)
ans.push_back(true);
else
ans.push_back(false);
}
return ans;
}
};
Временная сложность здесь равна O(n)+O(n) = O(n)один раз для обхода и нахождения максимума, а другой – для сравнения того, что значение больше, чем максимальное значение конфеты или нет.
Сложность пространства равна O(n), потому что я использую его для хранения логических значений.
