געפֿינען די סמאָלאַסט דיווייסער מיט אַ שוועל לעעטקאָדע לייזונג


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַפּפּדינאַמיקס גוגל זאַפט וואַלמאַרט לאַבס
LeetCode

דער פּאָסטן איז אויף געפֿינען די סמאָלאַסט דיווייסער מיט אַ שוועל לעעטקאָדע לייזונג

פּראָבלעם דערקלערונג

אין דעם פּראָבלעם "געפֿינען די סמאָלאַסט דיווייסער געגעבן אַ שוועל" מיר באַקומען אַ נומס מענגע און אַ שוועל ווערט. א בייַטעוודיק "רעזולטאַט" איז דיפיינד ווי די סומע פון ​​אַלע ענטפֿערס ווען עלעמענטן אין די מענגע זענען צעטיילט דורך אַ דיווייזער. אונדזער אַרבעט איז צו געפֿינען די קלענסטער מעגלעך ווערט פון די דיווייזער אַזוי אַז דער רעזולטאַט איז קלענערער ווי אָדער גלייַך צו די שוועל.

ווען מיר טיילן די עלעמענטן אין די מענגע דורך אַ דיווייזער, מיר באַטראַכטן די סטעליע ווערט ווי די ענטפער צו דיוויזשאַן. דיוויזאָר זאָל זיין אַ positive ינטאַדזשער.

בייַשפּיל

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 ווייַל די דיווייזער איז אַ positive ינטאַדזשער.
  • אויב מיר רעדן וועגן די מאַקסימום ווערט פון די דיווייסער, מיר קענען דערגרייכן דעם מאַקסימום ווערט אין די נומס מענגע ווייַל וואַלועס גרעסער ווי דאָס וועט אויך שטענדיק געבן די זעלבע ענטפער.

געפֿינען די סמאָלאַסט דיוויזאָר מיט אַ שוועל לעעטקאָדע לייזונג

  • איצט מיר האָבן די מינימום און די מאַקסימום ווערט פון דיווייזער אין אונדזער האַנט. איצט אונדזער בלויז אַרבעט איז צו געפֿינען די סמאָלאַסט דיוויזאָר.
  • מיר קענען מאַניואַלי קאָנטראָלירן פֿאַר יעדער ווערט אין די [מין, מאַקס] קייט, אָבער ווי די וואַלועס אין די קייט זענען אויסגעשטעלט אַזוי מיר נוצן אַ ביינערי זוכן אַלגערידאַם פֿאַר בעסער צייט קאַמפּלעקסיטי.
  • מיר זענען טריינג צו געפֿינען אויס די סמאָלאַסט ווערט פון די דיווייזער, אַזוי די שלייף וועט סוף ווען אָנהייב <= סוף. אין די סוף, די אָנהייב כּולל די לעצט ענטפֿערן, אַזוי מיר וועלן צוריקקומען זייַן ווערט.

קאָדעקס

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 איז די לענג פון די נומס מענגע.

אָרט קאַמפּלעקסיטי

אָ (1) ווייַל מיר נוצן זכּרון בלויז צו קראָם דעם ענטפער.

רעפֿערענצן