Айналдырылған массивті шешім кодынан іздеу


Күрделілік дәрежесі орта
Жиі кіреді Adobe Alibaba Amazon алма Bloomberg ByteDance Cisco еВау Expedia Facebook Голдман Сакс Google JPMorgan LinkedIn Microsoft Нутаниx NVIDIA Oracle PayPal Paytm Salesforce Samsung ServiceNow Tencent Tesla TripAdvisor Twitch қиятын виза VMware Walmart зертханалары Yahoo Яндекс Zillow Зулили
Array Екілік іздеу

Сұрыпталған массивті қарастырайық, бірақ бір индекс таңдалған және сол кезде жиым айналдырылған. Енді массивті айналдырғаннан кейін белгілі бір мақсатты элементті тауып, оның индексін қайтару керек. Егер элемент жоқ болса, -1 қайтарыңыз. Мәселе, әдетте, «Айналдырылған сұрыпталған массивтің шешім кодында іздеу» деп аталады. Сұрақта бізге белгілі емес индекс бойынша сұрыпталған және айналдырылған кейбір бүтін элементтер массиві ұсынылған. Массивпен бірге бізге табу керек белгілі бір элемент те беріледі.

Айналдырылған массивті шешім кодынан іздеу

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 қайтарамыз. Тәсіл өте қарапайым, бірақ ол массивтің бір индекс бойынша сұрыпталған және айналатындығын қолданбағандықтан. Бұл тәсіл уақыттың сызықтық күрделілігіне ие.

Айналмалы сұрыпталған массивтің іздеу коды

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

Күрделілікті талдау

Уақыттың күрделілігі

O (N), өйткені нашар жағдайда мақсатты элемент массивтің соңында болуы мүмкін. Осылайша уақыттың күрделілігі сызықтық болып табылады.

Ғарыштың күрделілігі

O (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

Күрделілікті талдау

Уақыттың күрделілігі

O (журнал N), өйткені біз мақсатты элементті табу үшін екілік іздеуді қолдандық. Уақыттың күрделілігі логарифмдік болып табылады.

Ғарыштың күрделілігі

O (1), өйткені біз тек кейбір элементтердің тұрақты санын сақтадық, кеңістіктің күрделілігі тұрақты.