Намерете най-малкия делител с дадено решение за праг Leetcode


Ниво на трудност M
Често задавани в AppDynamics Google SAP Walmart Labs
LeetCode

Тази публикация е на Намерете най-малкия делител, получил решение за праг Leetcode

Изявление на проблема

В задачата „Намерете най-малкия делител с даден праг“ получаваме масив от числа и прагова стойност. Променлива „резултат“ се дефинира като сбор от всички отговори, когато елементите в масива са разделени от делител. Нашата задача е да намерим възможно най-малката стойност на делителя по такъв начин, че резултатът да е по-малък или равен на прага.

Когато разделяме елементите в масива на делител, ние разглеждаме стойността на тавана като отговор на делението. Делителят трябва да бъде a положително цяло число.

Пример

arr=[1,2,5,9], threshold=6
5

Обяснение: когато разделяме всички елементи на 1 резултат е (1 + 2 + 5 + 9) 17, което е по-голямо от 6. И така, ще увеличим стойността на делителя, за да намалим стойността на резултата.

Сега, ако разгледаме делител = 4, тогава резултатът е (1 + 1 + 2 + 3) 7, което е по-голямо от 6. И така, ще увеличим стойността на делителя, за да намалим стойността на резултата.

ако разгледаме делител = 5, тогава резултатът е (1 + 1 + 1 + 2) 6. Значи отговорът е 5.

Подход

Нашата задача е да намерим Минималната стойност на делителя. И така, нека първо помислим какво може да бъде минимум и максимум стойност на делителя.

  • Минималната стойност на делителя е 1, защото делителят е положително цяло число.
  • Говорейки за максималната стойност на делителя, можем да го отрежем до максималната стойност в масива nums, защото стойности, по-големи от това, също винаги ще дадат един и същ отговор.

Намерете най-малкия делител с дадено решение за праг Leetcode

  • Сега имаме минимум и максимум стойност на делителя в нашата ръка. Сега единствената ни задача е да намерим най-малкия делител.
  • Можем ръчно да проверяваме за всяка стойност в диапазона [min, max], но тъй като стойностите в диапазона са сортирани, така че ще използваме Алгоритъм за двоично търсене за по-добра сложност във времето.
  • Опитваме се да открием най-малката стойност на делителя, така че цикълът ще завърши, когато start <= end. В крайна сметка началото ще съдържа окончателния отговор, така че ще върнем стойността му.

код

C ++ код за намиране на най-малкия делител с дадено решение за праг Leetcode

#include <bits/stdc++.h> 
using namespace std; 
   int smallestDivisor(vector<int>& nums, int threshold) {
        int s=1,e=*max_element(nums.begin(),nums.end());
        int n=nums.size();
        while(s<=e)
        {
            int mid=s+(e-s)/2;
            int sum=0;
            for(int i=0;i<n;i++)
                sum=sum+(nums[i]+mid-1)/mid;
            if(sum<=threshold)
            {
                e=mid-1;
            }
            else
            {
                s=mid+1;
            }
                
        }
        return s;
    }

int main() 
{ 
 vector<int> arr = {1,2,5,9}; 
 int threshold = 6;
 cout<<smallestDivisor(arr,threshold)<<endl; 
 return 0;
}
5

Java код за намиране на най-малкия делител, даден с решение за праг Leetcode

import java.util.Arrays; 
public class Tutorialcup {
 public static  int smallestDivisor(int[]  nums, int threshold) {
        int s=1,e=Arrays.stream(nums).max().getAsInt();
        int n=nums.length;
        while(s<=e)
        {
            int mid=s+(e-s)/2;
            int sum=0;
            for(int i=0;i<n;i++)
                sum=sum+(nums[i]+mid-1)/mid;
            if(sum<=threshold)
            {
                e=mid-1;
            }
            else
            {
                s=mid+1;
            }
                
        }
        return s;
    }

  public static void main(String[] args) {
    int [] arr = {1,2,5,9}; 
    int threshold = 6;
    int ans=  smallestDivisor(arr,threshold);
    System.out.println(ans);
  }
}

 

5

Анализ на сложността на намирането на най-малкия делител, даден с решение за праг Leetcode

Времева сложност

Сложността във времето на горния код е О (п) защото обхождаме масива nums само веднъж. Тук n е дължината на масива nums.

Космическа сложност

O (1) защото използваме памет само за съхраняване на отговора.

Препратки