फिरवलेल्या क्रमवारीबद्ध अ‍ॅरे लीटकोड सोल्यूशनमध्ये शोधा


अडचण पातळी मध्यम
वारंवार विचारले अडोब Alibaba ऍमेझॉन सफरचंद ब्लूमबर्ग बाइट डान्स सिस्को हा कोड eBay यामध्ये फेसबुक गोल्डमन Sachs Google जेपी मॉर्गन, संलग्न मायक्रोसॉफ्ट न्युटॅनिक्स , NVIDIA ओरॅकल पोपल पेटीएम सेल्सबॉल्स सॅमसंग सेवा Tencent टेस्ला कामांची चौकशी करण्याची मागणी हिसका उबेर व्हिसा व्हीएमवेअर वॉलमार्ट लॅब याहू यांडेक्स झिलो झुलीली
अरे बायनरी शोध

क्रमवारी लावलेल्या अ‍ॅरेचा विचार करा परंतु एक निर्देशांक निवडला गेला आणि त्या बिंदूत अ‍ॅरे फिरविला गेला. आता एकदा अ‍ॅरे फिरवला की आपल्याला एखादा विशिष्ट लक्ष्य घटक शोधण्याची आणि तिची अनुक्रमणिका परत मिळवणे आवश्यक आहे. जर घटक अस्तित्त्वात नसेल तर परतावा -1. या समस्येस सामान्यत: सर्च इन फिरवलेले सॉर्ट केलेले अ‍ॅरे लीटकोड सोल्यूशन असे म्हणतात. तर प्रश्नामध्ये, आम्हाला काही पूर्णांक तत्त्वांची अ‍ॅरे प्रदान केली गेली आहेत जी आम्हाला न कळणार्‍या एका विशिष्ट निर्देशांकात सॉर्ट आणि फिरविली जातात. अ‍ॅरेसमवेत आम्हाला शोधण्यासाठी आवश्यक असलेला एक विशिष्ट घटक देखील देण्यात आला आहे.

फिरवलेल्या क्रमवारीबद्ध अ‍ॅरे लीटकोड सोल्यूशनमध्ये शोधा

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

स्पष्टीकरणः शोधला जाणारा घटक is आहे. घटक index निर्देशांकात आढळला आहे म्हणून आम्ही लक्ष्यांची अनुक्रमणिका परत करतो.

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

स्पष्टीकरणः घटक अ‍ॅरेमध्ये नसल्यामुळे आपण परत -1.

फिरवलेल्या क्रमवारी लावलेल्या अ‍ॅरेमध्ये शोधासाठी ब्रूट फोर्स दृष्टीकोन

“फिरवलेल्या क्रमवारीबद्ध अ‍ॅरेमध्ये शोधा” ही समस्या आम्हाला दिलेल्या फिरवलेल्या सॉर्ट केलेल्या अ‍ॅरेमध्ये लक्ष्य घटकाची अनुक्रमणिका शोधण्यास सांगते. आणि आम्ही आधीच चर्चा केली आहे की फिरवलेले सॉर्ट केलेले अ‍ॅरे म्हणजे काय? म्हणूनच, सोपा पध्दत ज्याचा आपण विचार करू शकता ती म्हणजे रेखीय शोध. रेखीय शोध मध्ये, आम्ही फक्त दिलेला ओलांडतो अॅरे आणि सद्य घटक आपला लक्ष्य घटक आहे की नाही ते तपासा. जर सद्य घटक लक्ष्य घटक असेल तर आम्ही वर्तमान निर्देशांक परत करतो अन्यथा आम्ही परत करतो -1. दृष्टिकोन अगदी सोपा आहे परंतु हे एका निर्देशांकात अ‍ॅरेची क्रमवारी लावून फिरविण्यात आल्याचा उपयोग करत नाही. या दृष्टिकोनात रेषीय वेळ गुंतागुंत आहे.

फिरवलेल्या क्रमवारीबद्ध अ‍ॅरे लीटकोड सोल्यूशनमध्ये शोधासाठी कोड

सी ++ कोड

#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);
}
0

जावा कोड

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));
    }
}
0

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण सर्वात वाईट परिस्थितीत अ‍ॅरेच्या शेवटी लक्ष्य घटक उपस्थित असू शकतो. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (1), आम्ही प्रत्येक घटकासंदर्भात कोणतीही माहिती विशेषतः देत नसल्यामुळे आणि सतत व्हेरिएबल्स वापरत आहोत. अशा प्रकारे जागेची जटिलता स्थिर आहे.

फिरवलेल्या क्रमवारी लावलेल्या अ‍ॅरेमध्ये शोधासाठी ऑप्टिमाइझ केलेला दृष्टीकोन

पूर्वी नमूद केलेला दृष्टिकोन अ‍ॅरे फिरलेला क्रमवारी लावलेला अ‍ॅरे आहे हे वापरला नाही. तर, या दृष्टिकोनातून आम्ही ही वस्तुस्थिती वेळ गुंतागुंत कमी करण्यासाठी वापरण्याचा प्रयत्न करतो. विचार करा, जर आपल्याकडे क्रमवारी लावता आली असेल तर आपण फक्त वापरला असता बायनरी शोध परंतु जर हे थोडे अवघड आहे. येथे देखील आम्हाला बायनरी शोध वापरण्याची आवश्यकता आहे. परंतु जर आपण बायनरी शोध वापरत असाल तर अ‍ॅरेच्या मधल्या घटकात एकदा अ‍ॅरेचा कोणता भाग निवडायचा हे आम्हाला कसे कळेल? कारण आम्ही केवळ मूळ बायनरी शोध अल्गोरिदम अनुसरण करू शकत नाही कारण हा फिरलेला क्रमवारी लावलेला आहे. तर, सामान्य बायनरी शोधात थोडीशी बदल करण्यात आली आहेत.

तर, विशेषत: बायनरी शोधात, आम्ही तपासतो की विद्यमान घटक (मध्य निर्देशांकातील घटक) लक्ष्याइतकाच आहे की नाही तर आम्ही त्याची अनुक्रमणिका परत करतो. ही पायरी येथे कायम आहे. त्याखेरीज, जर ते सारखे नसतील तर आपण पिव्होट उजवीकडे [विद्यमान घटकाच्या डावीकडे किंवा डावीकडे आहे का ते तपासतो. जर ते उजवीकडे पडले असेल तर आम्ही लक्ष्य न फिरवलेल्या सबॅरेमध्ये आहे की नाही हे तपासले आहे, जर आम्ही ते उच्च अद्यतनित केले नाही तर आम्ही कमी अद्यतनित करतो. त्याचप्रमाणे, मुख्य पिशवी डावीकडे असल्यास, पुन्हा आम्ही तपासले आहे की लक्ष्य नॉन-फिरवलेल्या सबॅरेमध्ये आहे की नाही हे आम्ही कमी अद्यतनित करतो, नाही तर आम्ही उच्च अद्यतनित करतो. आणि शेवटी, जर आपण लूपमधून बाहेर पडलो तर आपल्याला खात्री आहे की दिलेल्या अ‍ॅरेमध्ये लक्ष्य अस्तित्त्वात नाही.

फिरवलेल्या क्रमवारीबद्ध अ‍ॅरे लीटकोड सोल्यूशनमध्ये शोधासाठी ऑप्टिमाइझ कोड

सी ++ कोड

#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);
}
0

जावा कोड

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));
    }
}
0

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (लॉग एन), आम्ही लक्ष्य घटक शोधण्यासाठी बायनरी शोध वापरला आहे. वेळेची जटिलता म्हणजे लॉगरिथमिक.

स्पेस कॉम्प्लेक्सिटी

ओ (1), आम्ही केवळ काही स्थिर घटकांची संचयित केली असल्याने, जागा अवघडपणा स्थिर आहे.