ترټولو کوچنی تقسیم کونکی د لیسکوډ حل لاره ورکړئ ومومئ


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي د AppDynamics د ګوګل د تبليغاتو د د وال مارټ لیبز
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 دی ځکه چې تقاعد یو مثبت عدد دی.
  • د تقویم د اعظمي ارزښت په اړه خبرې کول موږ کولی شو دا د شمیرو صفونو کې اعظمي ارزښت ته ټرم کړو ځکه چې له دې څخه ډیر ارزښتونه به همیشه ورته ځواب درکړي.

ترټولو کوچنی ډیووزر وموندئ چې د حد لټکوډ حل یې ورکړ

  • اوس موږ لرو لږترلږه او اعظمي زموږ په لاس کې د تفرقه اچونې ارزښت. اوس زموږ یوازینۍ دنده د کوچني کوچنۍ تقطیر موندل دي.
  • موږ کولی شو د [دقیقې ، اعظمي] حد کې د هر ارزښت لپاره په لاسي ډول وګورو مګر لکه څنګه چې د اندازې ارزښتونه ترتیب شوي نو موږ به یې وکاروو د دوه لمبر لټون الګوریتم د غوره وخت پیچلتیا لپاره.
  • موږ هڅه کوو چې د تقویم کوچنۍ ارزښت ومومئ نو لوپ به پای ته ورسیږي کله چې <<پای پای ته ورسیږي. په پای کې ، پیل به وروستی ځواب ولري نو موږ به یې ارزښت بیرته راستون کړو.

کوډ

د کوچنۍ کوچنۍ برخې موندلو لپاره C ++ کوډ د لیسټکوډ حل لاره ورکړل شوی

#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

د لږ کوچني تقویم موندلو لپاره جاوا کوډ د لټکوډ حل لاره ورکړل شوی

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

د پیچلي تحلیل تحلیل ترټولو کوچني ډیوژنر ته ورکړ شوی لټکوډ حل

د وخت پیچلتیا

د پورتنۍ کوډ وخت پیچلتیا ده اې (N) ځکه چې موږ یوازې یو ځل د شمیرو صف څخه تیروو. دلته n د شمیرو د اوږدوالي اوږدوالی دی.

د ځای پیچلتیا

O (1) ځکه چې موږ یوازې د ځواب ذخیره کولو لپاره حافظه کاروو.

ماخذونه