Որոնեք պտտվող տեսակավորված զանգվածի 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 Զուլին
Դասավորություն Երկուական որոնում

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

Որոնեք պտտվող տեսակավորված զանգվածի 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:

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

«Փնտրել պտտվող տեսակավորված զանգվածում» խնդիրը խնդրում է մեզ գտնել տվյալ պտտվող տեսակավորված զանգվածում նպատակային տարրի ինդեքսը: Եվ մենք արդեն քննարկել ենք, թե ինչ է պտտվող տեսակավորված զանգվածը: Այսպիսով, ամենապարզ մեթոդը, որի մասին կարելի է մտածել, գծային որոնումն է: Գծային որոնման մեջ մենք ուղղակի անցնում ենք տրվածը դասավորություն և ստուգեք ՝ արդյո՞ք ընթացիկ տարրը մեր նպատակային տարրն է: Եթե ​​ընթացիկ տարրը նպատակային տարր է, մենք վերադարձնում ենք ընթացիկ ցուցանիշը, այլապես մենք վերադարձնում ենք -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);
}
0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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