1431. Kids With the Greatest Number of Candies (使用 C 語言解題)

1431. Kids With the Greatest Number of Candies

Solved

Easy

Topics

Companies

Hint

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

 

Example 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.

Example 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.

Example 3:

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

 

Constraints:

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

 

google 翻譯：

有 n 個拿著糖果的孩子。 給你一個整數數組 candies，其中每個 candies[i] 代表第 i 個孩子擁有的糖果數量，
以及一個整數 extraCandies，表示你擁有的額外糖果數量。傳回一個長度為 n 的布林數組結果，其中，
如果在給第 i 個孩子所有額外糖果後，他們將擁有所有孩子中最多的糖果，則 result[i] 為 true，否則為 false。

請注意，多個孩子可以擁有最多數量的糖果。

想法一：

要一塊記憶體（題目要求），並把結果存放在裡面，供最後回傳。
首先找出數組中的最大值，記起來。
再把自己的糖果，依序給每一個小孩，並比較剛剛找出的最大值，
將結果存入要回傳的記憶體中，並回傳。

寫法一：

bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize) {
    int i, max = 0;
    // 要一塊記憶體，存結果，並回傳用
    char *result = malloc(sizeof(char) * candiesSize);

    // 找出數組中的最大值，記在變數 max
    for(i=0; i<candiesSize; i++) {
        if(candies[i] > max)
            max = candies[i];
    }
    
    // 把自己的糖果，依序+到每個小孩，比較 max，並存入記憶體中
    for(i=0; i<candiesSize; i++) {
        result[i] = ((candies[i]+extraCandies) >= max) ? 1 : 0;
    }
    
    // 設定回傳個數，並回傳結果
    *returnSize = candiesSize;
    return result;
}

結果一：

速度和記憶體都在中間值，再找看看有沒有別的方法...

想法二：

找數組中的最大值，如果 for 少跑一次會快多少呢？

寫法二：

bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize) {
    int i, max = candies[0]; // max 給陣列第一個當初始值
    char *result = malloc(sizeof(char) * candiesSize);

    // 找出數組中的最大值，迴圈從 1 開始
    for(i=1; i<candiesSize; i++) {
        if(candies[i] > max)
            max = candies[i];
    }
    for(i=0; i<candiesSize; i++) {
        result[i] = ((candies[i]+extraCandies) >= max) ? 1 : 0;
    }
    *returnSize = candiesSize;
    return result;
}

結果二：

竟然還比剛剛慢，這是真的嗎...

想法三：

去看看大神的寫法，看有什麼改進的方法。看起來跟我這寫法是一樣的，我再試一次剛剛寫法好了...

寫法三：

bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize) {
    int i, max = 0;
    // 要一塊記憶體，存結果，並回傳用
    char *result = malloc(sizeof(char) * candiesSize);

    // 找出數組中的最大值，記在變數 max
    for(i=0; i<candiesSize; i++) {
        if(candies[i] > max)
            max = candies[i];
    }

    // 把自己的糖果，依序+到每個小孩，比較 max，並存入記憶體中
    for(i=0; i<candiesSize; i++) {
        result[i] = ((candies[i]+extraCandies) >= max) ? 1 : 0;
    }

    // 設定回傳個數，並回傳結果
    *returnSize = candiesSize;
    return result;
}

結果三：

一樣的寫法，結果突然變的很好，我也覺得納悶。可能我跑結果的同時，是不是也有人同時在跑影響的？？總之，之後多跑幾次看看...