केथ मिसिंग पॉजिटिव नंबर लेटकोड सॉल्यूशन


कठिनाई स्तर आसान
में अक्सर पूछा Facebook माइक्रोसॉफ्ट
ऐरे hashing

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

"केटी मिसिंग पॉजिटिव नंबर" समस्या में हमें एक अरैस्ट अरेस्ट दिया जाता है, जिसे क्रमबद्ध किया जाता है सख्ती बढ़ रही है आदेश और एक नंबर कश्मीर।

हमारा कार्य सरणी में Kth सकारात्मक लापता संख्या का पता लगाना है।

उदाहरण

arr = [1,2,3,4], k = 2
6

स्पष्टीकरण:

केथ मिसिंग पॉजिटिव नंबर लेटकोड सॉल्यूशन

जैसा कि दिए गए ऐरे में, पहली अनुपलब्ध संख्या 5 है और दूसरी लापता संख्या है। 6. तो, उत्तर 6 है।

ब्रूट फोर्स एकेटी मिसिंग पॉजिटिव नंबर लेटकोड सॉल्यूशन के लिए pproach

इस समस्या को हल करने के लिए जानवर बल दृष्टिकोण इस प्रकार है:

  1. सरणी को पीछे छोड़ें।
  2. हर बार हम गुम संख्या की गणना करेंगे।
  3. यदि अनुपलब्ध धनात्मक संख्याओं की संख्या k के बराबर या उससे अधिक है तो हम i + k वापस कर देंगे।
  4. सरणी के पूर्ण ट्रावेल के बाद यदि लापता तत्वों की संख्या k से कम है तो हम सरणी + k का आकार वापस कर देंगे।

कार्यान्वयन

केटी मिसिंग पॉजिटिव नंबर के लिए सी ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
    int findKthPositive(vector<int>& arr, int k) {
        for(int i=0;i<arr.size();i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.size()+k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

केटी मिसिंग पॉजिटिव नंबर के लिए जावा कोड

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] arr, int k) {
        for(int i=0;i<arr.length;i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.length+k;
    }   
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

केटी मिसिंग पॉजिटिव नंबर लेटकोड सॉल्यूशन की जटिलता विश्लेषण

समय की जटिलता

उपरोक्त कोड की समय जटिलता है पर) क्योंकि हम एक रैखिक खोज का उपयोग कर रहे हैं जो सबसे खराब स्थिति में O (n) समय लेती है। यहाँ n दी गई सरणी की लंबाई है।

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

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

बाइनरी सर्च एकेटी मिसिंग पॉजिटिव नंबर लेटकोड सॉल्यूशन के लिए pproach

उपरोक्त एल्गोरिथ्म की समय जटिलता हे (एन) है क्योंकि हमें सबसे खराब स्थिति में पूर्ण सरणी को पीछे करने की आवश्यकता हो सकती है। हम रैखिक खोज के स्थान पर द्विआधारी खोज का उपयोग करके समाधान की समय जटिलता में सुधार कर सकते हैं।

  1. आइए पहले द्विआधारी खोज के लिए हमारी खोज की सीमा को परिभाषित करें। तो प्रारंभ इंडेक्स 0 होगा और अंत दिए गए एरे का अंतिम इंडेक्स होगा।
  2. हमें मिड इंडेक्स मिल जाएगा तब हम जांचेंगे कि क्या लापता पॉजिटिव की संख्या k से कम है:
    1. फिर शुरू मध्य + 1 हो जाएगा।
    2. और अंत मध्य हो जाएगा।
  3. वापसी अंत + के।

कार्यान्वयन

केटी मिसिंग पॉजिटिव नंबर के लिए सी ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
int findKthPositive(vector<int>& A, int k) {
        int l = 0, r = A.size(), m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

केटी मिसिंग पॉजिटिव नंबर के लिए जावा कोड

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] A, int k) {
        int l = 0, r = A.length, m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }  
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

केटी मिसिंग पॉजिटिव नंबर लेटकोड सॉल्यूशन की जटिलता विश्लेषण

समय की जटिलता

उपरोक्त कोड की समय जटिलता है O (लॉग एन) क्योंकि हम एक बाइनरी खोज का उपयोग कर रहे हैं जो सबसे खराब स्थिति में O (logn) समय लेता है। यहाँ n दी गई सरणी की लंबाई है।

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

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

संदर्भ