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

  1. Tárolja a nums tömb maximális elemét a maxElement változóban.
  2. Iterálás minden divisors-on 1-től maxElement-ig:
  • Inicializáljon két változót, sumOfDivisionResults - 0, hogy hozzáadja az osztás eredményét az egyes tömbelemekhez, és
    thresholdExceeded - 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 a sumOfDivisionResults változóban, és ha az összeg meghaladja a threshold értéket, jelölje meg a thresholdExceeded értéket true-ként, és állítsa le az iterációt a nums 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ális divisor a legkisebb osztó, ezért adja vissza.
  1. 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

  1. Ha az osztási eredmények összege current divisor-vel nagyobb, mint az threshold, akkor az összeg nagyobb lesz minden osztó esetén, amely kisebb, mint current divisor (mert ha csökkentjük a nevezőt, a teljes eredmény növekedni fog), ezért azt sugallja, hogy csak az current divisor jobb oldalán kell keresnünk (azaz current divisor-nál nagyobb számok esetén).
  2. Hasonlóképpen, ha az osztási eredmények összege current divisor értékkel kisebb, mint threshold, akkor az összeg minden osztó esetén kisebb lesz, mint current 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

  1. Határozzon meg egy findDivisionSum(nums, divisor) függvényt az osztási eredmények összegének visszaadásához.
  2. Változók inicializálása:
  • ans = -1, egész szám a legalacsonyabb osztó tárolására, amely nem haladja meg a threshold é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.
  1. Bináris keresés alkalmazása a low és high 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 a threshold-t, akkor a válasz mid lehet.
    Tehát frissítsd a ans-et mid-el, de lehetnek kisebb lehetséges osztóink is, így frissítsd a high-t mid - 1-re. (a mid 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 a low-at mid + 1-re (a mid-tól balra lévő elemeket el kell dobni).
  1. 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⋅log⁡M)
  • A tér összetettsége: O(1).