घुमाएँ क्रमबद्ध ऐरे लेटकोड समाधान में खोजें  


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब अलीबाबा वीरांगना सेब ब्लूमबर्ग ByteDance सिस्को ईबे Expedia Facebook गोल्डमैन सैक्स गूगल जेपी मॉर्गन लिंक्डइन माइक्रोसॉफ्ट Nutanix Nvidia ओरेकल पेपैल Paytm Salesforce सैमसंग अभी मरम्मत करें Tencent टेस्ला TripAdvisor चिकोटी Uber देखना VMware वॉलमार्ट लैब्स याहू Yandex Zillow ज़ुल्ली
एल्गोरिदम ऐरे द्विआधारी खोज कोडिंग साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस

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

घुमाएँ क्रमबद्ध ऐरे लेटकोड समाधान में खोजेंपिन

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

स्पष्टीकरण: चूंकि खोजा जाने वाला तत्व 4 है। तत्व 0 पर पाया जाता है, हम लक्ष्य के सूचकांक को वापस करते हैं।

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

स्पष्टीकरण: चूंकि तत्व सरणी में मौजूद नहीं है, इसलिए हम -1 लौटते हैं।

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

समस्या "घुमाए हुए क्रमबद्ध एरे में खोजें" हमें दिए गए घुमाए गए सरणी में लक्ष्य तत्व के सूचकांक को खोजने के लिए कहती है। और हमने पहले से ही चर्चा की है कि एक घुमाया गया सरणी क्या है? तो, सबसे सरल विधि जो किसी के बारे में सोच सकती है वह है रैखिक खोज की कोशिश करना। रैखिक खोज में, हम बस दिए गए को पीछे छोड़ते हैं सरणी और जांचें कि क्या वर्तमान तत्व हमारा लक्ष्य तत्व है। यदि वर्तमान तत्व लक्ष्य तत्व है, तो हम वर्तमान सूचकांक को वापस लौटाते हैं-और हम -1 लौटते हैं। दृष्टिकोण बहुत सरल है लेकिन चूंकि यह इस तथ्य का उपयोग नहीं करता है कि सरणी को एक ही सूचकांक में क्रमबद्ध और घुमाया जाता है। इस दृष्टिकोण में रैखिक समय की जटिलता है।

यह भी देखें
एन-थ ट्रिबोनैचि नंबर लेटकोड सॉल्यूशन

कोड में खोज के लिए घुमाया सॉर्ट किया गया Leetcode समाधान

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

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

समय जटिलता

पर), क्योंकि सबसे बुरी स्थिति में, लक्ष्य तत्व सरणी के अंत में मौजूद हो सकता है। इस प्रकार समय जटिलता रैखिक है।

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

ओ (1), क्योंकि हम विशेष रूप से प्रत्येक तत्व के संबंध में कोई जानकारी नहीं रखते हैं और निरंतर संख्या में चर का उपयोग करते हैं। इस प्रकार अंतरिक्ष जटिलता स्थिर है।

अनुकूलित क्रमबद्ध एरे में खोज के लिए अनुकूलित दृष्टिकोण  

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

इसलिए, आम तौर पर एक द्विआधारी खोज में, हम जांचते हैं कि क्या वर्तमान तत्व (मध्य सूचकांक में तत्व) लक्ष्य के समान है, तो हम इसके सूचकांक को वापस करते हैं। यह कदम यहीं रहता है। इसके अलावा, यदि वे समान नहीं हैं, तो हम जांचते हैं कि क्या धुरी वर्तमान तत्व के दाईं ओर या बाईं ओर स्थित है। यदि यह दाईं ओर स्थित है, तो हम जाँचते हैं कि क्या लक्ष्य नॉन-रोटेटेड सबअरे में है, यदि यह उच्च को अद्यतन करता है तो हम निम्न को अद्यतन करते हैं। इसी तरह, यदि पिवट बाईं ओर स्थित है, तो फिर से हम जाँचते हैं कि क्या लक्ष्य नॉन-रोटेटेड सबरे में निहित है, हम निम्न को अपडेट करते हैं, अन्यथा हम उच्च को अपडेट करते हैं। और अंत में, यदि हम लूप से बाहर आते हैं, तो हम सुनिश्चित हैं कि लक्ष्य दिए गए ऐरे में मौजूद नहीं है।

यह भी देखें
Sqrt (एक्स) Leetcode समाधान

अनुकूलित क्रमबद्ध ऐरे लेटकोड समाधान में खोज के लिए अनुकूलित कोड

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 (लॉग एन), चूंकि हमने लक्ष्य तत्व को खोजने के लिए द्विआधारी खोज का उपयोग किया है। समय जटिलता लॉगरिदमिक है।

यह भी देखें
किन्हीं दो तत्वों के बीच न्यूनतम अंतर ज्ञात कीजिए

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

ओ (1), चूंकि हमने केवल कुछ स्थिर तत्वों को संग्रहीत किया है, इसलिए अंतरिक्ष जटिलता स्थिर है।