Шукайце ў паварочаным сартаваным масіве рашэння Leetcode


Узровень складанасці серада
Часта пытаюцца ў Саман Alibaba амазонка яблык Bloomberg ByteDance Cisco eBay Expedia facebook Goldman Sachs Google JPMorgan LinkedIn Microsoft Нутанікс Nvidia Аракул PayPal Paytm Salesforce Samsung ServiceNow Tencent Цеслы TripAdvisor Тузацца Uber Віза VMware Лабараторыі Walmart Yahoo Яндэкс Zillow Зулілы
масіў Двайковы пошук

Разгледзім адсартаваны масіў, але быў выбраны адзін індэкс і масіў павярнуты ў гэты момант. Цяпер, як толькі масіў быў павернуты, вам трэба знайсці пэўны мэтавы элемент і вярнуць яго індэкс. У выпадку, калі элемента няма, вярніце -1. Праблема звычайна называецца Пошук у паварочаным сартаваным масіве з рашэннем кода. Такім чынам, у пытанні мы атрымліваем масіў некаторых цэлых лікаў, якія сартуюцца і паварочваюцца з пэўным індэксам, які нам не вядомы. Разам з масівам нам таксама дадзены пэўны элемент, які нам трэба знайсці.

Шукайце ў паварочаным сартаваным масіве рашэння 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. Падыход вельмі просты, але, паколькі ён не выкарыстоўвае той факт, што масіў сартуецца і паварочваецца па адным індэксе. Такі падыход мае лінейную часавую складанасць.

Код для пошуку ў паварочаным сартаваным масіве

Код 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), паколькі мы не маем інфармацыі адносна кожнага элемента і выкарыстоўвалі пастаянную колькасць зменных. Такім чынам, касмічная складанасць сталая.

Аптымізаваны падыход да пошуку ў паваротным сартаваным масіве

Раней згаданы падыход не выкарыстоўваў той факт, што масіў быў павярнутым адсартаваным масівам. Такім чынам, у гэтым падыходзе мы спрабуем выкарыстаць гэты факт, каб паменшыць складанасць часу. Падумайце, калі б у нас быў адсартаваны масіў, мы б проста выкарысталі яго бінарны пошук але ў выпадку, калі гэта крыху складана. Тут мы таксама павінны выкарыстоўваць бінарны пошук. Але калі мы выкарыстоўваем двайковы пошук, як даведацца, якую частку масіва выбраць, апынуўшыся ў сярэднім элеменце масіва? Паколькі мы не можам проста прытрымлівацца зыходнага алгарытму двайковага пошуку, таму што гэта павярнуты адсартаваны масіў. Такім чынам, ёсць невялікая мадыфікацыя звычайнага бінарнага пошуку.

Такім чынам, звычайна пры бінарным пошуку мы правяраем, ці адпавядае бягучы элемент (элемент у сярэднім індэксе) мэтавай, і вяртаем яго індэкс. Тут гэты крок застаецца ранейшым. Апроч гэтага, калі яны не аднолькавыя, мы правяраем, ці ляжыць шарнір справа [ад бягучага элемента альбо злева. Калі ён ляжыць направа, то мы правяраем, ці ляжыць мэта ў нявернутым падмасіве, калі гэта адбываецца, мы абнаўляем высокае, у іншым выпадку мы абнаўляем нізкае. Аналагічна, калі стрыжань ляжыць злева, мы зноў правяраем, ці ляжыць мэта ў невернутым падмасіве, мы абнаўляем нізкі ўзровень, у адваротным выпадку мы абнаўляем высокі. І ў рэшце рэшт, калі мы выходзім з цыкла, мы ўпэўненыя, што мэты няма ў дадзеным масіве.

Аптымізаваны код для пошуку ў паварочаным сартаваным масіве

Код 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), паколькі мы захоўваем толькі нейкую нязменную колькасць элементаў, складанасць прасторы пастаянная.