מצא את המחלק הקטן ביותר שקיבל פתרון Leetcode סף


רמת קושי בינוני
נשאל לעתים קרובות AppDynamics Google SAP מעבדות וולמארט
LeetCode

פוסט זה נמצא ב מצא את המחלק הקטן ביותר שקיבל פתרון Leetcode סף

הצהרת בעיה

בבעיה "מצא את המחלק הקטן ביותר בהתחשב בסף" אנו מקבלים מערך nums וערך סף. משתנה "תוצאה" מוגדר כסכום של כל התשובות כאשר אלמנטים במערך מחולקים על ידי מחלק. המשימה שלנו היא למצוא את הערך הקטן ביותר האפשרי של המחלק באופן שהתוצאה תהיה קטנה או שווה לסף.

כאשר אנו מחלקים את האלמנטים במערך בחלוקה, אנו רואים את ערך התקרה כתשובה לחלוקה. מחלק צריך להיות א מספר שלם חיובי.

דוגמה

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] אך כאשר הממוינים את הערכים בטווח כך נשתמש ב- אלגוריתם חיפוש בינארי למורכבות זמן טובה יותר.
  • אנו מנסים לברר את הערך הקטן ביותר של המחלק, כך שהלולאה תסתיים עם התחלה <= סוף. בסופו של דבר ההתחלה תכיל את התשובה הסופית ולכן נחזיר את ערכה.

קופונים

קוד 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 סף

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n) מכיוון שאנחנו עוברים את מערך ה- nums פעם אחת בלבד. כאן n הוא אורך מערך ה- nums.

מורכבות חלל

O (1) כי אנו משתמשים בזיכרון רק כדי לאחסן את התשובה.

הפניות