leetcode 1431e 拥有最多糖果的孩子

Published on:
Tags: leetcode

题目描述#

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

示例：

1
2
3
4
5
6
7
8
输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true] 
解释：
孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。

提示：

  • 2 <= candies.length <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50

即是：

  • 2 <= 孩子的数量 <= 100
  • 1 <= 孩子的糖果数量 <= 100
  • 1 <= 额外的糖果数量 <= 50

算法#

  1. 遍历每个小孩子的糖果数量，找到糖果数量最大值 maximum
  2. 把额外的糖果数量只分给一个小孩，找到此时糖果总数量 大于等于 糖果数量最大值 的小孩

C代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
typedef int bool;

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize)
{
    int i;
    int maximum = 0;
    bool *output = (bool *)malloc(sizeof(bool) * candiesSize);

    // 遍历每个小孩子的糖果数量，找到糖果数量最大值 maximum
    for(i=0;i<candiesSize;i++)
    {
        if(candies[i] > maximum) maximum = candies[i];
    }

    //  把额外的糖果数量 extraCandies 只分给一个小孩，
    //  找到此时糖果总数量 大于等于 糖果数量最大值 的小孩，标记true，其余标记false
    for(i=0;i<candiesSize;i++)
    {
        if (candies[i] + extraCandies >= maximum)
            output[i] = true;
        else
            output[i] = false;
    }

    *returnSize = candiesSize;
    return output;    
}



int main()
{
    int candies[] = {1,2,3,4,5,6,7,8};
    int candiesSize = 8;
    int extraCandies = 2;
    int *returnSize;
    bool *result;
    result = kidsWithCandies(&candies[0],candiesSize,extraCandies,returnSize);
    printf("[");
    for(int i=0;i<*returnSize;i++)
    {
        if(result[i] == 1)
            printf("true");
        else
            printf("false");
        
        if(i < (*returnSize-1)) printf(",");
    }
    printf("]");
    free(result);
}

时间复杂度#

第一次for循环，时间复杂度为O(n)；

第二次for循环，时间复杂度也为O(n)。

因此算法的时间复杂度为O(n)。