घुमाइएको क्रमबद्ध एर्रे लेटकोड समाधानमा खोजी गर्नुहोस्  


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब Alibaba अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स सिस्को eBay Expedia फेसबुक Goldman सैक्स गुगल जेपी मर्गन LinkedIn माइक्रोसफ्ट नुटानिक्स NVIDIA बजेट PayPal पेटम SalesForce Samsung अब सेवा Tencent tesla TripAdvisor झटका Uber भिषा VMware वालमार्ट ल्याबहरू याहू Yandex Zillow जलिली
एल्गोरिदम एरे बाइनरी खोज कोडिंग अन्तर्वार्ता साक्षात्कार तयारी LeetCode LeetCodeSolutions

क्रमबद्ध गरिएको एर्रेलाई विचार गर्नुहोस् तर एउटा सूचकांक छानियो र एरे त्यस बिन्दुमा घुमाइएको थियो। अब, एक पटक एर्रे घुमाए पछि तपाईलाई विशेष लक्षित तत्व फेला पार्न र यसको अनुक्रमणिका फर्काउन आवश्यक छ। यदि मामलामा, एलिमेन्ट छैन, फिर्ता -१। समस्या सामान्यतया घुमाइएको क्रमबद्ध एर्रे लेटकोड समाधानमा खोजीको रूपमा सन्दर्भ गरिन्छ। त्यसोभए प्रश्नमा, हामीलाई केहि पूर्णा elements्क तत्वहरूको एर्रे प्रदान गरिन्छ जुन क्रमबद्ध र एक निश्चित अनुक्रमणिकामा घुमाइएको छ जुन हामीलाई थाहा छैन। एर्रेसँगै, हामीलाई एक विशिष्ट तत्व पनि दिइन्छ जुन हामीले फेला पार्न आवश्यक छ।

घुमाइएको क्रमबद्ध एर्रे लेटकोड समाधानमा खोजी गर्नुहोस्पिन

array: [4,5,6,7,0,1,2]
target: 4

स्पष्टीकरण: किनकि खोज्नु पर्ने तत्व is हो। तत्व ० सूचकांकमा फेला पर्‍यो, हामी लक्ष्यको अनुक्रमणिका फिर्ता गर्छौं।

array: [4,5,6,7,0,1,2]
target: 3
-1

स्पष्टीकरण: एलिमेन्ट एर्रेमा उपस्थित नभएकोले हामी फर्क्यौं -१।

घुमाइएको क्रमबद्ध एर्रेमा खोजीको लागि ब्रुट फोर्स दृष्टिकोण  

समस्या "घुमाइएको क्रमबद्ध एर्रेमा खोजी गर्नुहोस्" हामीलाई दिइएको घुमाइएको क्रमबद्ध एर्रेमा लक्ष्य तत्वको अनुक्रमणिका फेला पार्न सोध्छ। र हामीले पहिले नै छलफल गरिसकेका घुमाइएको क्रमबद्ध एर्रे के हो? त्यसोभए, सोच्न सक्ने सबैभन्दा सरल विधि भनेको लिनियर खोज प्रयास गर्नु हो। रेखीय खोजमा, हामी केवल दिइएको पार गर्छौं array र जाँच गर्नुहोस् कि यदि वर्तमान तत्व हाम्रो लक्ष्य तत्व हो। यदि हालको तत्व लक्ष्य तत्व हो भने हामी हालको सूचकांक फिर्ता गर्छौं अन्यथा हामी फर्केका छौं। दृष्टिकोण धेरै सरल छ तर यसले एरेलाई एकल सूचकांकमा क्रमबद्ध र रोटेट गरिएको तथ्यलाई प्रयोग गर्दैन। यस दृष्टिकोणमा रेखा समय जटिलता छ।

पनि हेर्नुहोस्
N-th Tribonacci संख्या लेटकोड समाधान

घुमाइएको क्रमबद्ध एर्रे लेटकोड समाधानमा खोजीको लागि कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    int n = nums.size();
    for(int i=0;i<n;i++)
        if(nums[i] == target)
            return i;
    return -1;
}

int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        for(int i=0;i<n;i++)
            if(nums[i] == target)
                return i;
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}

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

समय जटिलता

O (N), किनभने सबैभन्दा खराब अवस्थामा, लक्ष्य तत्व एर्रेको अन्त्यमा उपस्थित हुन सक्छ। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (१), किनकि हामी प्रत्येक तत्व विशेषको बारेमा कुनै जानकारी छैनौं र लगातार चल संख्याहरूको प्रयोग गरेका छौं। यसैले ठाउँ जटिलता स्थिर छ।

घुमाइएको क्रमबद्ध एर्रेमा खोजीको लागि अनुकूलित दृष्टिकोण  

माथि उल्लेखित दृष्टिकोणले एरे घुमाएको क्रमबद्ध एर्रे हो भन्ने तथ्यलाई प्रयोग गर्दैन। त्यसो भए यस दृष्टिकोणमा हामी यो तथ्यलाई समयको जटिलता कम गर्न प्रयोग गर्ने कोशिश गर्छौं। विचार गर्नुहोस्, यदि हामीसँग क्रमबद्ध एर्रे भएको भए, हामी सजिलै प्रयोग गर्न सक्दछौं बाइनरी खोज तर यदि यो अलि कठिन छ। यहाँ पनि हामीलाई बाइनरी खोज प्रयोग गर्न आवश्यक छ। तर यदि हामीले बाइनरी खोजी प्रयोग गर्यौं भने एर्रेको कुन भागलाई छनौट गर्ने भनेर हामी कसरी थाहा पाउन सक्छौं एरेको मध्य एलिमेन्टमा पुगे पछि? किनकि हामी केवल मूल बाइनरी खोज एल्गोरिथ्म अनुसरण गर्न सक्दैनौं किनकि यो घुमाइएको क्रमबद्ध एर्रे हो। त्यसो भए, त्यहाँ सामान्य बाइनरी खोजीमा हल्का परिमार्जन छ।

त्यसोभए, प्राय: बाइनरी खोजीमा हामी जाँच गर्छौं यदि हालको तत्व (मध्य सूचकांकमा एलिमेन्ट) लक्ष्यको रूपमा समान छ, तब हामी यसको सूचकांक फिर्ता गर्छौं। यो चरण यहीं रहन्छ। त्यस बाहेक, यदि ती समान छैनन् भने, हामी जाँच गर्छौं कि पिभोट दायाँ [वर्तमान तत्वको वा बायाँ पट्टी छ)। यदि यो सहि रहेको छ भने, हामी जाँच गर्छौं यदि लक्षित गैर-घुमाइएको सबारीमा रहेको छ, यदि यसले हामीले उच्च अपडेट गर्‍यौं भने हामी कम अपडेट गर्छौं। त्यस्तै गरी, यदि पिभोट बाँयामा छ भने, फेरि हामी जाँच गर्छौं यदि लक्षित गैर-घुमाइएको सबार्रेमा छ भने, हामी कम अपडेट गर्छौं, नत्र हामी उच्च अपडेट गर्छौं। र अन्तमा, यदि हामी लुपबाट बाहिर आउँछौं, हामी निश्चय छौं कि लक्षित एर्रेमा लक्षित छैन।

पनि हेर्नुहोस्
Sqrt (x) लीटकोड समाधान

घुमाइएको क्रमबद्ध एर्रे लेटकोड समाधानमा खोजीको लागि अनुकूलित कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    int n = nums.size();
    int low = 0, high = n-1;
    while(low<=high){
        int mid = (low+high)/2;
        // check if the current element is target
        if(nums[mid] == target)
            return mid;
        // if the starting index of the search space has smaller element than current element
        else if(nums[low]<=nums[mid]){
            // if target lies in non-rotated search space (or subarray)
            if(target >= nums[low] && target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            // if target lies in non-rotated subarray
            if(target>nums[mid] && target<=nums[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    // if you couldn't find the target element until now then it does not exists
    return -1;
}
int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        int low = 0, high = n-1;
        while(low<=high){
            int mid = (low+high)/2;
            // check if the current element is target
            if(nums[mid] == target)
                return mid;
            // if the starting index of the search space has smaller element than current element
            else if(nums[low]<=nums[mid]){
                // if target lies in non-rotated search space (or subarray)
                if(target >= nums[low] && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                // if target lies in non-rotated subarray
                if(target>nums[mid] && target<=nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        // if you couldn't find the target element until now then it does not exists
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}

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

समय जटिलता

ओ (लग एन), हामीले लक्ष्य तत्व फेला पार्न बाइनरी खोज प्रयोग गरेका छौं। समय जटिलता लघुगणक हो।

पनि हेर्नुहोस्
कुनै पनि दुई तत्वहरु बीच न्यूनतम फरक खोज्नुहोस्

ठाउँ जटिलता

O (१), किनकि हामीले केही तत्वहरूको संख्या मात्र भण्डारण गरेका छौं, स्पेस जटिलता स्थिर छ।