題目描述:給定一個整數陣列 nums 和一個整數 threshold,找出一個最小的正整數除數,使得所有 ceil(nums[i] / divisor) 的總和不超過 threshold。
解題思路:這是一道典型的「二分搜尋答案」題型。除數越大,各元素除後的上取整值越小,總和也越小;除數越小則總和越大,具備單調性。因此可以對答案範圍 [1, max(nums)] 做二分搜尋:對每個候選除數 mid,計算 sum(ceil(nums[i] / mid)) 是否 ≤ threshold。若是,代表 mid 可能是答案,嘗試更小的值;否則需要更大的除數。注意上取整可用 (nums[i] + mid - 1) / mid 在整數運算中完成,避免浮點數誤差。
時間複雜度:O(n log(max(nums))) — 二分搜尋範圍為 [1, max(nums)],共 O(log(max(nums))) 輪;每輪的 feasible 函數線性掃描陣列,耗時 O(n)。
空間複雜度:O(1) — 只使用常數個額外變數,不計輸入本身。
1. Set lo = 1, hi = max(nums) 2. While lo < hi: a. mid = lo + (hi - lo) / 2 b. Compute total = sum of ceil(num / mid) for each num in nums c. If total <= threshold: hi = mid (mid is feasible, try smaller) d. Else: lo = mid + 1 (mid too small, need larger divisor) 3. Return lo
方法一:暴力枚舉 — O(n * max(nums)) 從除數 1 開始逐一往上試,計算每個除數對應的總和,找到第一個使總和 ≤ threshold 的除數即為答案。時間複雜度 O(n * max(nums)),在 max(nums) 達到 10^6 時會超時,不實用但概念直觀。
方法二:前綴和輔助 — O(n log(max(nums))) 若數值範圍已排序,可以利用前綴和快速計算某除數下各「值域區間」的貢獻,但實作複雜度高且常數較大,實際效能不如直接二分搜尋搭配線性掃描,僅在特殊場景(如多次查詢)有優勢。
threshold 等於陣列長度(即 n),最小除數會是什麼?能否直接推導而不需要二分搜尋?max(nums) 的理由是什麼?若改成 sum(nums) 作為上界,正確性是否依然成立?對效能有何影響?