Чектик Leetcode Чечими берилген эң кичинекей бөлгүчтү табыңыз


Кыйынчылык деңгээли орто
Көп суралган AppDynamics Гугл SAP Walmart Labs
LeetCode

Бул пост Босого Leetcode Чечими берилген Кичинекей Бөлүшчүнү табуу боюнча

Көйгөйдү айтуу

“Босого берилген эң кичинекей бөлүүчүнү табуу” маселесинде бизге сан массиви жана босого мааниси берилет. Массивдеги элементтер бөлүштүргүчкө бөлүнгөндө, "натыйжа" өзгөрмөсү бардык жооптордун суммасы катары аныкталат. Биздин милдет - бөлүнгүчтүн эң кичине маанисин, натыйжа, босогодон кичине же ага барабар кылып табуу.

Массивдеги элементтерди бөлгүчкө бөлгөндө, шыптын маанисин бөлүнүүгө жооп деп эсептейбиз. Бөлүүчү а болушу керек оң сан.

мисал

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

Explanation: бардык элементтерди 1 натыйжага бөлгөндө (1 + 2 + 5 + 9) 17, 6дан чоңураак болот, демек, натыйжанын маанисин азайтуу үчүн бөлүүчүнүн маанисин көбөйтөбүз.

Эми бөлгүчтү = 4 деп эсептесек, анда натыйжа (1 + 1 + 2 + 3) 7 болот, ал 6дан чоң болот. Ошентип, натыйжанын маанисин азайтуу үчүн бөлүүчүнүн маанисин көбөйтөбүз.

эгер биз бөлүүчү = 5 деп эсептесек, анда натыйжа (1 + 1 + 1 + 2) 6. Демек, жооп 5 болот.

жакындоо

Биздин милдет - табуу минималдуу маани бөлүүчүнүн. Ошентип, алгач эмне болушу мүмкүн экендигин ойлонуп көрөлү минимум жана максимум бөлүүчүнүн мааниси.

  • Бөлүүчүнүн минималдуу мааниси 1, анткени бөлүүчү оң бүтүн сан.
  • Бөлүүчүнүн максималдуу мааниси жөнүндө сөз кылганда, аны nums массивиндеги максималдуу мааниге чейин кыскарта алабыз, анткени андан чоң маанилер дагы бирдей жооп берет.

Leitcode чечиминин босогосу берилген эң кичинекей бөлгүчтү табыңыз

  • Азыр бизде минимум жана максимум биздин колубуздагы бөлүүчүнүн мааниси. Эми биздин бирден-бир милдетибиз - эң кичинекей бөлүүчүнү табуу.
  • [Min, max] диапазонундагы ар бир маанини кол менен текшере алабыз, бирок диапазондогу маанилер иреттелгендиктен, биз колдонобуз Бинардык издөө алгоритми убакыттын татаалдыгы үчүн.
  • Бөлгүчтүн эң кичине маанисин билүүгө аракет кылып жатабыз, ошондуктан цикл башталгандан кийин бүтөт <= аяктаганда. Акыр-аягы, старт акыркы жоопту камтыйт, ошондуктан биз анын маанисин кайтарабыз.

коду

Leitcode чечими берилген эң кичинекей бөлүүчүнү табуу үчүн 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

Leitcode чечиминин босогосу берилген эң кичинекей бөлүүчүнү табуу үчүн Java коду

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

Leitcode чечими берилген эң кичинекей бөлүүчүнү табуунун татаалдыгын талдоо

Убакыттын татаалдыгы

Жогорудагы коддун убакыттын татаалдыгы O (N) анткени биз нумдар массивин бир жолу гана кыдырып жатабыз. Бул жерде n - сан массивинин узундугу.

Космостун татаалдыгы

O (1) анткени биз эс тутумду жоопту сактоо үчүн гана колдонобуз.

шилтемелер