सॉर्ट किए गए एरे लेटकोड सॉल्यूशन में एलीमेंट का पहला और आखिरी स्थान खोजें  


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना ब्लूमबर्ग ByteDance Facebook गूगल माइक्रोसॉफ्ट ओरेकल Uber
एल्गोरिदम ऐरे कोडिंग साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस

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

सॉर्ट किए गए एरे लेटकोड सॉल्यूशन में एलीमेंट का पहला और आखिरी स्थान खोजें, शीर्षक से इस लेख में, हम लेटकोड समस्या के समाधान पर चर्चा करेंगे। दी गई समस्या में हमें एक सरणी दी गई है। हमें एक लक्ष्य तत्व भी दिया जाता है। सरणी में तत्व बढ़ते क्रम में क्रमबद्ध हैं।

हमें क्रमबद्ध सरणी में लक्ष्य तत्व की पहली और अंतिम स्थिति को खोजने की आवश्यकता है।

यदि लक्ष्य तत्व मौजूद नहीं है, तो [-1, -1] वापस लौटें।

उदाहरण  

array: [1,2,5,5,5,9] , target=5
[2,4]

स्पष्टीकरण:

सॉर्ट किए गए एरे लेटकोड सॉल्यूशन में एलीमेंट का पहला और आखिरी स्थान खोजेंपिन

दिए गए सॉर्ट किए गए ऐरे की तरह, 5 पहली बार इंडेक्स नंबर 2 पर और आखिरी बार इंडेक्स नंबर 4 में दिखाई देता है।

दृष्टिकोण  

इस समस्या को हल करने के लिए अनुभवहीन दृष्टिकोण पूरे सरणी को स्कैन करना और सूचकांक को वापस करना है जब हम पहली बार और आखिरी बार लक्ष्य का सामना करते हैं। इस एल्गोरिथ्म के लिए समय की जटिलता हे (एन) के रूप में सबसे खराब स्थिति में हमें पूर्ण सरणी को पार करने की आवश्यकता हो सकती है।

चूंकि तत्वों को बढ़ते क्रम में क्रमबद्ध किया जाता है, हम इसका लाभ उठा सकते हैं। रैखिक खोज करने के बावजूद, हम एक का उपयोग करेंगे बाइनरी सर्च लक्ष्य तत्व की पहली और अंतिम घटनाओं को खोजने के लिए। यह बाइनरी सर्च कोड सामान्य बाइनरी सर्च कोड से थोड़ा अलग होगा, जहां हम जांचते हैं कि तत्व सॉर्ट किए गए ऐरे में मौजूद है या नहीं।

यह भी देखें
Q प्रश्नों की अगली ग्रेटर संख्या प्रिंट करें

सामान्य बाइनरी सर्च कोड में ये छोटे बदलाव हैं:

  1. लक्ष्य तत्व को खोजने के तुरंत बाद कार्यक्रम समाप्त नहीं होगा। हम प्रारंभ = अंत तक लूप चलाएंगे।
  2. एक और बदलाव उस बिंदु पर है जहां गिरफ्तारी [मध्य] == लक्ष्य।
    1. पहली घटना के अंत के लिए = मध्य -1।
    2. और अंतिम घटना के लिए प्रारंभ = मध्य + 1।

कोड सॉर्ट किए गए ऐरे लेटकोड सॉल्यूशन में एलीमेंट का पहला और आखिरी स्थान खोजें  

C ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
    int findFirst(vector<int>& nums, int target)
    {
         int ans = -1;
    int s = 0;
    int e = nums.size() - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            e = mid - 1;
        }
    }
    return ans;
    }
     int findLast(vector<int>& nums, int target)
    {
          int ans = -1;
    int s = 0;
    int e = nums.size() - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            s = mid + 1;
        }
    }
    return ans;
    }
    vector<int> find(vector<int>& nums, int target) {
        vector<int>result(2);
         result[0] = findFirst(nums, target);
         result[1] = findLast(nums, target);
         return result;
    }

int main() 
{ 
 vector<int> arr = {1,2,5,5,5,9}; 
int target=5;
vector<int> ans(2);
ans=  find(arr,target);
for(int i=0;i<2;i++)
 cout<<ans[i]<<" "; 
 return 0;
}
[2,4]

जावा कोड

import java.util.Arrays; 
public class Tutorialcup {
    public static int[] find(int[] nums, int target) {
    int[] result = new int[2];
    result[0] = findFirst(nums, target);
    result[1] = findLast(nums, target);
    return result;
}

private static int findFirst(int[] nums, int target){
    int ans = -1;
    int s = 0;
    int e = nums.length - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            e = mid - 1;
        }
    }
    return ans;
}
    

private static int findLast(int[] nums, int target){
       int ans = -1;
    int s = 0;
    int e = nums.length - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            s = mid + 1;
        }
    }
    return ans;
}
  public static void main(String[] args) {
    int [] arr = {1,2,5,5,5,9}; 
    int target=5;
     int[] ans = new int[2];
    ans=  find(arr,target);
    System.out.println(Arrays.toString(ans));
  }
}
[2,4]

जटिलता विश्लेषण  

समय की जटिलता

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

यह भी देखें
ऐरे लेटकोड सॉल्यूशन में लकी इंटेगर का पता लगाएं

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

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

संदर्भ