მოიძიეთ დალაგებული მასივის Leetcode ამოხსნა


Რთული ტური საშუალო
ხშირად ეკითხებიან Adobe Alibaba Amazon Apple Bloomberg ByteDance Cisco eBay Expedia Facebook Goldman Sachs Google JPMorgan LinkedIn microsoft ნუტუნიქსი Nvidia Oracle PayPal Paytm Salesforce Samsung სერვისი Tencent Tesla TripAdvisor Twitch Uber Visa VMware Walmart Labs Yahoo Yandex Zillow ზულილი
Array ორობითი ძებნა

განვიხილოთ დახარისხებული მასივი, მაგრამ აიყვანეს ერთი ინდექსი და მასივი გადატრიალდა ამ ეტაპზე. მასივის შემობრუნების შემდეგ თქვენ მოგიწევთ იპოვოთ კონკრეტული სამიზნე ელემენტი და დააბრუნოთ მისი ინდექსი. იმ შემთხვევაში, თუ ელემენტი არ არის, დააბრუნე -1. პრობლემა ზოგადად მოიხსენიება, როგორც ძებნა მბრუნავ დალაგებულ მასივში Leetcode Solution. ამ კითხვაში, ჩვენ მოგვაწოდეთ მთელი რიგი მთელი ელემენტების მასივი, რომლებიც დალაგებულია და ბრუნავს ჩვენთვის უცნობ გარკვეულ ინდექსზე. მასივთან ერთად ჩვენ გვეძლევა კონკრეტული ელემენტიც, რომლის პოვნაც უნდა.

მოიძიეთ დალაგებული მასივის Leetcode ამოხსნა

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

განმარტება: ვინაიდან მოსაძიებელი ელემენტია 4. ელემენტი გვხვდება ინდექსში 0, ჩვენ ვაბრუნებთ სამიზნის ინდექსს.

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

განმარტება: რადგან ელემენტი არ არის მასივში, ვბრუნდებით -1.

უხეში ძალის მიდგომა ძებნაში მობრუნებულ დალაგებულ მასივში

პრობლემა ”ძებნა მბრუნავ დალაგებულ მასივში” გვთხოვს მოცემული მობრუნებული დალაგებული მასივის სამიზნე ელემენტის ინდექსის პოვნას. და ჩვენ უკვე განვიხილეთ რა არის დატრიალებული დახარისხებული მასივი? ასე რომ, უმარტივესი მეთოდი, რომელზეც შეიძლება ვიფიქროთ, არის ხაზოვანი ძიების ცდა. ხაზოვანი ძიებისას, ჩვენ უბრალოდ გადავკვეთთ მოცემულს მასივი და შეამოწმეთ არის თუ არა ამჟამინდელი ელემენტი ჩვენი სამიზნე ელემენტი. თუ ამჟამინდელი ელემენტია სამიზნე ელემენტი, ჩვენ დავაბრუნებთ მიმდინარე ინდექსს, თუ ჩვენ დავაბრუნებთ -1. მიდგომა ძალიან მარტივია, მაგრამ მასში არ გამოიყენება ის ფაქტი, რომ მასივი დალაგებულია და ბრუნავს ერთ ინდექსზე. ამ მიდგომას აქვს ხაზოვანი დროის სირთულე.

მობრუნებული დალაგებული მასივის Leetcode Solution- ში ძიების კოდი

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

სირთულის ანალიზი

დროის სირთულე

O (N), რადგან უარეს შემთხვევაში, სამიზნე ელემენტი შეიძლება იყოს მასივის ბოლოს. ამრიგად, დროის სირთულე წრფივია.

სივრცის სირთულე

O (1)რადგან ჩვენ არ გვაქვს ინფორმაცია კონკრეტულად თითოეულ ელემენტთან დაკავშირებით და გამოვიყენეთ ცვლადების მუდმივი რაოდენობა. ამრიგად, სივრცის სირთულე მუდმივია.

მობრუნებული დალაგებული მასივის ძიების ოპტიმიზებული მიდგომა

ადრე აღნიშნულ მიდგომაში არ გამოიყენება ის ფაქტი, რომ მასივი იყო მობრუნებული დალაგებული მასივი. ამ მიდგომით, ჩვენ ვცდილობთ გამოვიყენოთ ეს ფაქტი დროის სირთულის შესამცირებლად. გაითვალისწინეთ, რომ დახარისხებული მასივი გვქონდეს, უბრალოდ გამოვიყენებდით ორობითი ძებნა იმ შემთხვევაში, თუ ეს ცოტა რთულია. აქ ასევე ჩვენ უნდა გამოვიყენოთ ორობითი ძებნა. მაგრამ თუ ვიყენებთ ორობით ძიებას, როგორ უნდა გავიგოთ, თუ მასივის რომელი ნაწილი უნდა აირჩიოთ მას შემდეგ, რაც მასივის შუა ელემენტზე ვიქნებით? რადგან ჩვენ არ შეგვიძლია უბრალოდ დავიცვათ ორიგინალური ორობითი ძიების ალგორითმი, რადგან ეს არის მობრუნებული დალაგებული მასივი. ასე რომ, ოდნავი ცვლილება ხდება ნორმალური ორობითი ძიების დროს.

ასე რომ, როგორც წესი, ორობითი ძიებისას ვამოწმებთ, არის თუ არა ამჟამინდელი ელემენტი (ელემენტი შუა ინდექსში) იგივეა, რაც სამიზნე, მაშინ ჩვენ ვუბრუნებთ მის ინდექსს. ეს ნაბიჯი აქ იგივე რჩება. გარდა ამისა, თუ ისინი არ არიან ერთი და იგივე, ჩვენ ვამოწმებთ, არის თუ არა კრუნჩხალი მარჯვნივ [ამჟამინდელი ელემენტისგან ან მარცხნივ. თუ ეს მარჯვნივ მდებარეობს, მაშინ ვამოწმებთ, არის თუ არა სამიზნე არა-მობრუნებული ქვეჯგუფში, თუ არ ვაახლებთ მაღალს, თუ არა დაბალი. ანალოგიურად, თუ კრუნჩხვი მოთავსებულია მარცხნივ, ისევ ვამოწმებთ არის თუ არა სამიზნე არა-მობრუნებული ქვეჯგუფში, ვაახლებთ დაბალს, სხვაგან ვაახლებთ მაღალს. დაბოლოს, თუ გამოვდივართ მარყუჟიდან, დარწმუნებული ვართ, რომ სამიზნე არ არის მოცემულ მასივში.

ოპტიმიზირებული კოდი ძებნაში მბრუნავ დახარისხებულ მასივში Leetcode Solution

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

სირთულის ანალიზი

დროის სირთულე

O (შესვლა N), ვინაიდან ჩვენ გამოვიყენეთ ორობითი ძებნა სამიზნე ელემენტის მოსაძებნად. დროის სირთულე არის ლოგარითმული.

სივრცის სირთულე

O (1), მას შემდეგ, რაც ჩვენ შენახული გვაქვს მხოლოდ გარკვეული მუდმივი რაოდენობის ელემენტები, სივრცის სირთულე მუდმივია.