題目描述:有 n 個小朋友,candies[i] 是第 i 個小朋友的糖果數量,另有 extraCandies 顆額外糖果。對每個小朋友,判斷若將所有 extraCandies 都給他,他是否會擁有最多(或並列最多)的糖果數量。回傳長度 n 的布林陣列。
解題思路:首先找出目前所有小朋友中的最大糖果數 maxCandies。接著對每個小朋友 i,判斷 candies[i] + extraCandies >= maxCandies 是否成立。若成立表示他加上額外糖果後能達到或超越當前最大值,填入 true,否則填入 false。只需兩次線性遍歷,非常直觀。
時間複雜度: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 合併,但邏輯上仍是兩次掃描。