कोको खाने के केले Leetcode समाधान


कठिनाई स्तर मध्यम
में अक्सर पूछा Facebook
द्विआधारी खोज

समस्या का विवरण

समस्या "कोको खाने के केले" में हमें आकार n दिया जाता है जिसमें प्रत्येक ढेर में केले की संख्या होती है। एक घंटे में कोको सबसे अधिक केला खा सकता है। अगर उस मामले में ढेर में केला कम होता है, अगर कोको उस ढेर के सारे केले खत्म कर देता है, तो वह एक ही घंटे में दूसरे ढेर से केले खाना शुरू नहीं कर सकता।

H घंटे के भीतर कोको सभी केले खाना चाहता है। हमें K का न्यूनतम मान ज्ञात करना है।

उदाहरण

piles = [30,11,23,4,20], H = 6
23

स्पष्टीकरण: 

केले खाने के लिए लेकोकोड समाधान केले

6 घंटे में सभी केले खाने के लिए कोको इस तरह से केले खाएगा:

पहला घंटा: 23

दूसरा घंटा::

तीसरा घंटा: 11

चौथा घंटा: 23

पांचवें घंटे: 4

छठा घंटा: 20

कोको खाने के केले लेटेकोड समाधान के लिए दृष्टिकोण

इस समस्या को हल करने के लिए पहली और सबसे महत्वपूर्ण बात यह है कि टिप्पणियों को सामने लाया जाए। हमारे खोज अंतराल के लिए कुछ अवलोकन यहां दिए गए हैं:

  1. कोको को प्रति घंटे कम से कम एक केला खाना चाहिए। तो यह K का न्यूनतम मान है प्रारंभ
  2. हम केले की अधिकतम संख्या को सीमित कर सकते हैं कोको सभी बवासीर के ढेर में एक घंटे में केले की अधिकतम संख्या तक खा सकते हैं। तो यह K का अधिकतम मान है अंत।

अब हमारे पास अपना खोज अंतराल है। मान लीजिए कि अंतराल का आकार है लंबाई और बवासीर की संख्या है n.  अंतराल में प्रत्येक मूल्य की जांच करने के लिए भोली दृष्टिकोण हो सकता है। यदि K कोको के उस मूल्य के लिए H घंटे में सभी केले सफलतापूर्वक खा सकते हैं तो उनमें से न्यूनतम चुनें। भोले दृष्टिकोण के लिए समय जटिलता सबसे खराब स्थिति में लंबाई * n होगी।

हम रैखिक खोज के स्थान पर बाइनरी सर्च का उपयोग करके समय की जटिलता में सुधार कर सकते हैं।

समय जटिलता का उपयोग कर द्विआधारी खोज दृष्टिकोण लॉग (लंबाई) * n होगा।

कार्यान्वयन

कोको खाने के केले के लिए सी ++ कोड

#include <bits/stdc++.h>
using namespace std; 
       int minEatingSpeed(vector<int>& pile, int hour) {
        int left = 1, right = *max_element(pile.begin(),pile.end());;
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : pile) total += (p + mid - 1) / mid;
            if (total > hour) left = mid + 1; else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {30,11,23,4,20}; 
 int H=6;                               
 cout<<minEatingSpeed(arr,H)<<endl;
 return 0;
}
23

कोको खाने के केले के लिए जावा कोड

import java.util.Arrays; 
public class Tutorialcup {
    public static int minEatingSpeed(int[] piles, int H) {
        int left = 1, right =Arrays.stream(piles).max().getAsInt();
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : piles) total += (p + mid - 1) / mid;
            if (total > H) left = mid + 1; else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {30,11,23,4,20}; 
     int H=6; 
    int ans= minEatingSpeed(arr,H);
    System.out.println(ans);
  }
}
23

कोको खाने के केले Leetcode समाधान की जटिलता विश्लेषण

समय की जटिलता

उपरोक्त कोड की समय जटिलता है ओ (एन * लॉग (डब्ल्यू)) क्योंकि हम एक और डब्ल्यू के बीच एक द्विआधारी खोज का प्रदर्शन कर रहे हैं, यह लॉगडब्लू समय लेता है और प्रत्येक मूल्य के लिए, द्विआधारी खोज में, हम ढेर सरणी को ट्रेस कर रहे हैं। तो बवासीर सरणी logWed बार है यह समय जटिलता n * logW बनाता है। यहाँ n और W बवासीर की संख्या और ढेर में केले की अधिकतम संख्या है।

अंतरिक्ष की जटिलता

उपरोक्त कोड की अंतरिक्ष जटिलता है ओ (1) क्योंकि हम उत्तर को संग्रहीत करने के लिए केवल एक चर का उपयोग कर रहे हैं।

संदर्भ