Որոնեք պտտվող տեսակավորված զանգվածի Leetcode լուծում  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Alibaba Amazon խնձոր Bloomberg ByteDance Cisco eBay Expedia facebook Goldman Sachs-ը Google JPMorgan LinkedIn Microsoft Նութանիքս Nvidia Պատգամախոս PayPal Paytm Salesforce Samsung ServiceNow- ը Tencent Tesla TripAdvisor Ջղաձգություն Uber Visa VMware Walmart Labs Անտաշ անասուն նողկալի արարած Yandex Zillow Զուլին
ալգորիթմները Դասավորություն Երկուական որոնում կոդավորում հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions

Հաշվի առեք տեսակավորված զանգվածը, բայց ընտրվեց մեկ ցուցիչ, և զանգվածը պտտվեց այդ պահին: Այժմ զանգվածը պտտվելուց հետո ձեզանից պահանջվում է գտնել որոշակի թիրախային տարր և վերադարձնել դրա ինդեքսը: Եթե ​​տարրը առկա չէ, վերադարձիր -1: Խնդիրն ընդհանուր առմամբ նշվում է որպես Որոնում պտտվող տեսակավորված զանգվածի Leetcode լուծում: Այսպիսով, հարցում մեզ տրամադրվում է մի շարք ամբողջ թվերի տարրերի զանգված, որոնք տեսակավորված են և պտտվում են որոշակի ինդեքսով, որը մեզ հայտնի չէ: Rayանգվածին զուգահեռ, մեզ նաև տրվում է որոշակի տարր, որը մենք պետք է գտնենք:

Որոնեք պտտվող տեսակավորված զանգվածի Leetcode լուծումPin

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

Բացատրություն. Քանի որ որոնման ենթակա տարրը 4 է. Տարրը գտնվում է 0 ինդեքսում, մենք հետ ենք վերադարձնում թիրախի ինդեքսը:

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

Բացատրություն. Քանի որ տարրը զանգվածում չկա, մենք վերադառնում ենք -1:

Պտտվող տեսակավորված զանգվածում որոնման համար Brute Force մոտեցում  

«Փնտրել պտտվող տեսակավորված զանգվածում» խնդիրը խնդրում է մեզ գտնել տվյալ պտտվող տեսակավորված զանգվածում նպատակային տարրի ինդեքսը: Եվ մենք արդեն քննարկել ենք, թե ինչ է պտտվող տեսակավորված զանգվածը: Այսպիսով, ամենապարզ մեթոդը, որի մասին կարելի է մտածել, գծային որոնումն է: Գծային որոնման մեջ մենք ուղղակի անցնում ենք տրվածը դասավորություն և ստուգեք ՝ արդյո՞ք ընթացիկ տարրը մեր նպատակային տարրն է: Եթե ​​ընթացիկ տարրը նպատակային տարր է, մենք վերադարձնում ենք ընթացիկ ցուցանիշը, այլապես մենք վերադարձնում ենք -1: Մոտեցումը շատ պարզ է, բայց քանի որ այն չի օգտագործում այն ​​փաստը, որ զանգվածը տեսակավորված է և պտտվում է մեկ ինդեքսով: Այս մոտեցումն ունի գծային ժամանակի բարդություն:

Տես նաեւ,
N- րդ տրիբոնաչիի համարի կոդերի լուծում

Պտտվող տեսակավորված զանգվածի 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);
}

Java կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ վատագույն դեպքում թիրախային տարրը կարող է առկա լինել զանգվածի վերջում: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

Ո (1), քանի որ մենք կոնկրետ որևէ տարրի վերաբերյալ որևէ տեղեկատվություն չունենք և օգտագործել ենք հաստատուն թվով փոփոխականներ: Այսպիսով, տարածության բարդությունը կայուն է:

Պտտվող տեսակավորված զանգվածում որոնման օպտիմիզացված մոտեցում  

Ավելի վաղ նշված մոտեցումը չի օգտագործում այն ​​փաստը, որ զանգվածը եղել է պտտվող տեսակավորված զանգված: Այսպիսով, այս մոտեցման մեջ մենք փորձում ենք օգտագործել այս փաստը `ժամանակի բարդությունը նվազեցնելու համար: Հաշվի առեք, որ եթե մենք տեսակավորված զանգված ունենայինք, ապա մենք պարզապես կօգտագործեինք երկուական որոնում բայց եթե դա մի փոքր բարդ է: Այստեղ նաև մեզանից պահանջվում է օգտագործել երկուական որոնում: Բայց եթե մենք օգտագործում ենք երկուական որոնում, ապա ինչպե՞ս իմանալ, թե զանգվածի որ մասն է ընտրելու, երբ գտնվենք զանգվածի միջին տարրում: Քանի որ մենք չենք կարող պարզապես հետևել երկուական որոնման բնօրինակ ալգորիթմին, քանի որ սա պտտվող տեսակավորված զանգված է: Այսպիսով, կա նորմալ երկուական որոնման փոքր փոփոխություն:

Այսպիսով, սովորաբար երկուական որոնման ժամանակ մենք ստուգում ենք ՝ արդյո՞ք ընթացիկ տարրը (տարրը միջին ինդեքսում) նույնն է, թե՞ թիրախը, ապա վերադարձնում ենք դրա ինդեքսը: Այս քայլն այստեղ մնում է նույնը: Բացի դրանից, եթե դրանք նույնը չեն, մենք ստուգում ենք ՝ առանցքը սուտ է [ընթացիկ տարրի աջից կամ ձախից: Եթե ​​այն գտնվում է աջ կողմում, ապա մենք ստուգում ենք ՝ արդյոք թիրախը գտնվում է ոչ պտտվող ենթաշղթայի մեջ, թե արդյոք մենք նորացնում ենք բարձրը, և մենք թարմացնում ենք ցածրը: Նմանապես, եթե առանցքը ընկած է ձախ կողմում, կրկին մենք ստուգում ենք ՝ արդյոք թիրախը գտնվում է ոչ պտտվող ենթադասում, մենք թարմացնում ենք ցածրը, այլապես բարձրացնում ենք բարձրը: Եվ վերջում, եթե մենք դուրս ենք գալիս օղակից, վստահ ենք, որ տվյալ զանգվածում թիրախը առկա չէ:

Տես նաեւ,
Sqrt (x) Leetcode լուծում

Օպտիմիզացված ծածկագիր `պտտվող տեսակավորված զանգվածի 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);
}

Java կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (տեղեկամատյան N), քանի որ մենք օգտագործել ենք երկուական որոնում ՝ նպատակային տարրը գտնելու համար: Timeամանակի բարդությունը լոգարիթմական է:

Տես նաեւ,
Գտեք նվազագույն տարբերությունը ցանկացած երկու տարրերի միջև

Տիեզերական բարդություն

O (1), քանի որ մենք պահպանում ենք միայն որոշ հաստատուն քանակի տարրեր, տարածության բարդությունը կայուն է: