解題說明
Kids With the Greatest Number of Candies
題目描述:有 n 個小朋友,candies[i] 是第 i 個小朋友的糖果數量,另有 extraCandies 顆額外糖果。對每個小朋友,判斷若將所有 extraCandies 都給他,他是否會擁有最多(或並列最多)的糖果數量。回傳長度 n 的布林陣列。
解題思路:首先找出目前所有小朋友中的最大糖果數 maxCandies。接著對每個小朋友 i,判斷 candies[i] + extraCandies >= maxCandies 是否成立。若成立表示他加上額外糖果後能達到或超越當前最大值,填入 true,否則填入 false。只需兩次線性遍歷,非常直觀。
C++ 解法
複雜度分析
時間複雜度:O(n) — 一次找最大值,一次遍歷生成結果。
空間複雜度:O(n) — 輸出布林陣列的大小為 n(不計輸出的話為 O(1))。
虛擬碼
1. Find maxCandies = max element in candies array 2. Initialize empty result array 3. For each c in candies: a. Append (c + extraCandies >= maxCandies) to result 4. Return result
其他解法
排序後二分搜尋:對 candies 排序,maxCandies 即為最後一個元素,邏輯相同但時間複雜度上升到 O(n log n),無實際優勢。
單次遍歷(合併兩步):先找 max 再判斷本就只需兩次 O(n) 遍歷,無法再縮短為一次(因為需要先知道最大值才能比較)。在某些函數式語言中可以用 fold 合併,但邏輯上仍是兩次掃描。
延伸思考
- 如果想讓每個小朋友得到的額外糖果不同(按某種分配策略),如何設計公平分配演算法?
- 若 extraCandies 也是一個陣列(第 i 個元素表示給第 i 個小朋友的額外糖果),如何修改解法?
- 此題的「最多」判斷採用 >= 而非 >,若改為嚴格最多(>),結果陣列會有何不同?