前往
大廳
主題

LeetCode - 1283. Find the Smallest Divisor Given a Threshold 解題心得

Not In My Back Yard | 2022-12-24 12:00:05 | 巴幣 100 | 人氣 170

題目連結:


題目意譯:
給定一整數陣列 nums 以及一整數 threshold,我們將選擇一正整數 divisor,將陣列中所有數字除以該數並加總所有除法的結果。找到最小的 divisor 使得前述的結果數值小於或等於 threshold。

每個除法的結果值將會被進位到大於或等於該元素的最近整數。(例如:7 ÷ 3 = 3 而 10 ÷ 2 = 5)。

測試資料之生成滿足答案必定存在。

限制:
1 ≦ nums.length ≦ 5 × 10 ^ 4
1 ≦ nums[i] ≦ 10 ^ 6
nums.length ≦ threshold ≦ 10 ^ 6



範例測資:
範例 1:
輸入: nums = [1,2,5,9], threshold = 6
輸出: 5
解釋: 如果 divisor 為 1,則我們可以得到一個總和值 17(1 + 2 + 5 + 9)。
如果 divisor 為 4,我們可以得到總和 7(1 + 1 + 2 + 3),而如果 divisor 為 5,則總和為 5(1 + 1 + 1 + 2)。

範例 2:
輸入: nums = [44,22,33,11,1], threshold = 5
輸出: 44


解題思維:
這題幾乎等價。本題的 threshold 與該題的 maxOperations 的角色一模一樣,但是計算猜的 m 值對於各個 nums[i] 需要多少「次」時,本題是「(nums[i] - 1) ÷ m」取整數部分後多加個 1(因為在本題中我們是「往上取整」)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作