Adott egy nums
és egy threshold
egész számokból álló tömb, kiválasztunk egy pozitív egész számot divisor
, elosztjuk vele az összes tömböt, és összeadjuk az osztás eredményét. Keresse meg a legkisebb divisor
értéket úgy, hogy a fent említett eredmény kisebb vagy egyenlő legyen, mint threshold
.
Az osztás minden eredményét az adott elemnél nagyobb vagy azzal egyenlő legközelebbi egész számra kerekítjük. (Például: 7/3 = 3
és 10/2 = 5
).
A tesztesetek úgy jönnek létre, hogy lesz válasz.
1. példa:
Input: nums = [1,2,5,9], threshold = 6 Output: 5 Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
2. példa:
Input: nums = [44,22,33,11,1], threshold = 5 Output: 44
Korlátozások:
1 <= nums.length <= 5 * 104
1 <= nums[i] <= 106
nums.length <= threshold <= 106
Áttekintés
Adunk egy nums
egész számot és egy threshold
egész számot, meg kell találnunk a lehető legkisebb divisor
értéket, amely a nums
tömb összes elemének felosztása esetén az osztások összege nem haladhatja meg a threshold
értéket.
Az osztás minden eredményét az adott elemnél nagyobb vagy azzal egyenlő legközelebbi egész számra kerekítjük.
Például: 7/3=2,33≈ (kerekítve) 3
Kezdjük először egy naiv megközelítésből, és optimalizáljuk tovább.
1. megközelítés: Lineáris keresés
Intuíció
Meg kell találnunk a lehető legkisebb divisor
-ot, így a lehető legkisebb osztóból indulhatunk ki, és ellenőrizhetjük, hogy miután az összes nums
tömbelemet ezzel divisor
osztjuk, az osztási eredmény összege nem haladja-e meg a threshold
-et, ha nem haladja meg, akkor ez lesz a legkisebb divisor
, így a válaszunk. Ellenkező esetben növeljük a divisor
értéket 1
-vel, és megismételjük ezt a lépést.
Tudjuk, hogy a lehető legkisebb osztó lehet 1
, de mi a helyzet a legnagyobbkal?
A threshold
minimális értéke megegyezik a nums
tömbmérettel. Ha az összes elemet felosztjuk a nums
tömb legnagyobb elemével, akkor az egyes osztások eredménye 1
lesz, és az osztások összege egyenlő lesz a nums
tömbmérettel, ami a threshold
legkisebb lehetséges értéke, tehát a felső korlát az osztók esetében a nums
tömb maximális eleme.
Most észreveheti, hogy az összes lehetséges osztót egyenként próbáljuk ki, így ez a megközelítés nagyon lassú, és várhatóan nem megy át minden teszteseten. De ez a megközelítés lesz a lépcsőfok az optimalizált megközelítés felé.
Algoritmus
- Tárolja a
nums
tömb maximális elemét amaxElement
változóban. - Iterálás minden
divisors
-on1
-tőlmaxElement
-ig:
- Inicializáljon két változót,
sumOfDivisionResults
-0
, hogy hozzáadja az osztás eredményét az egyes tömbelemekhez, ésthresholdExceeded
-false
, hogy jelezze, hogy túllépte-e a küszöbértéket. - Ismételje meg a
nums
tömb összes elemét, és adja hozzá az osztás eredményét a következő nagyobb egészre kerekítve asumOfDivisionResults
változóban, és ha az összeg meghaladja athreshold
értéket, jelölje meg athresholdExceeded
értékettrue
-ként, és állítsa le az iterációt anums
tömbön. - Ellenőrizze, hogy a
threshold
túllépése megtörtént-e vagy sem, ha nem lépte túl, akkor az aktuálisdivisor
a legkisebb osztó, ezért adja vissza.
- Ha soha nem találunk lehetséges osztót, akkor adja vissza a
-1
értéket.
Megvalósítás
Megjegyzés: A
divisionResult = ceil((1.0 * number) / divisor)
kódot használjuk a kívánt eredmény eléréséhez. De van egy klassz trükk arra, hogy az osztás eredményét a legközelebbi egész számra kerekítsük, amely nagyobb vagy egyenlő annál az elemnél, amely elkerüli a lebegő számokat és a lehetséges pontosságveszteséget,divisionResult = (number + divisor - 1) / divisor
használatával. Ezen módszerek bármelyikét használhatja a megvalósítás során.
class Solution { public int smallestDivisor(int[] nums, int threshold) { int maxElement = nums[0]; for (int num : nums) { maxElement = Math.max(maxElement, num); } // Iterate on all divisors. for (int divisor = 1; divisor <= maxElement; ++divisor) { int sumOfDivisionResults = 0; boolean thresholdExceeded = true; // Divide all numbers of array and sum the result. for (int num : nums) { sumOfDivisionResults += Math.ceil((1.0 * num) / divisor); if (sumOfDivisionResults > threshold) { thresholdExceeded = false; break; } } // If threshold was not exceeded then return current divisor. if (thresholdExceeded) { return divisor; } } return -1; } }
Bonyolultsági elemzés
Itt az N az elemek száma, az M pedig az nums
tömb maximális eleme.
- Időbeli összetettség: O(N⋅M).
- A tér összetettsége: O(1).
2. megközelítés: Bináris keresés
Intuíció
Az előző megközelítésben az összes lehetséges osztót egyenként iteráltuk, így nem volt hatékony.
Tehát most megpróbáljuk optimalizálni
- Ha az osztási eredmények összege
current divisor
-vel nagyobb, mint azthreshold
, akkor az összeg nagyobb lesz minden osztó esetén, amely kisebb, mintcurrent divisor
(mert ha csökkentjük a nevezőt, a teljes eredmény növekedni fog), ezért azt sugallja, hogy csak azcurrent divisor
jobb oldalán kell keresnünk (azazcurrent divisor
-nál nagyobb számok esetén). - Hasonlóképpen, ha az osztási eredmények összege
current divisor
értékkel kisebb, mintthreshold
, akkor az összeg minden osztó esetén kisebb lesz, mintcurrent divisor
(mert ha növeljük a nevezőt, az összeredmény csökken).
Így ez a két pont azt jelzi, hogy használhatjuk a bináris keresést az összes lehetséges osztó keresési területén 1
és maxElement
között.
Algoritmus
- Határozzon meg egy
findDivisionSum(nums, divisor)
függvényt az osztási eredmények összegének visszaadásához. - Változók inicializálása:
ans = -1
, egész szám a legalacsonyabb osztó tárolására, amely nem haladja meg athreshold
értéket.low = 1
, az összes lehetséges osztó keresési terének alsó korlátja.high = max element of nums
, az összes lehetséges osztó keresési terének felső korlátja.
- Bináris keresés alkalmazása a
low
éshigh
közötti keresési területen:
- Inicializálja a
mid
értéket a keresési tér középső értékével, azaz(low + high) / 2
. - Ellenőrizzük, hogy
mid
-et használunk-e osztóként, és ha nem haladja meg athreshold
-t, akkor a válaszmid
lehet.
Tehát frissítsd aans
-etmid
-el, de lehetnek kisebb lehetséges osztóink is, így frissítsd ahigh
-tmid - 1
-re. (amid
jobb oldalán lévő elemek elvetése). - Ellenkező esetben a
mid
túl kicsi, nagyobb osztóra van szükségünk, ezért frissítsd alow
-atmid + 1
-re (amid
-tól balra lévő elemeket el kell dobni).
- A végén térjen vissza a
ans
számmal.
class Solution { // Return the sum of division results with 'divisor'. private int findDivisionSum(int[] nums, int divisor) { int result = 0; for (int num : nums) { result += Math.ceil((1.0 * num) / divisor); } return result; } public int smallestDivisor(int[] nums, int threshold) { int ans = -1; int low = 1; int high = nums[0]; for (int num : nums) { high = Math.max(high, num); } // Iterate using binary search on all divisors. while (low <= high) { int mid = (low + high) / 2; int result = findDivisionSum(nums, mid); // If current divisor does not exceed threshold, // then it can be our answer, but also try smaller divisors // thus change search space to left half. if (result <= threshold) { ans = mid; high = mid - 1; } // Otherwise, we need a bigger divisor to reduce the result sum // thus change search space to right half. else { low = mid + 1; } } return ans; } }
Itt az N az elemek száma, az M pedig a nums
tömb maximális eleme.
- Időbonyolultság: O(N⋅logM)
- A tér összetettsége: O(1).