Ҷустуҷӯ дар ҳалли массиви гардонидашудаи Leetcode


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Alibaba Amazon себ Блумберг ByteDance Cisco мехаранд Expedia Facebook Голдман Sachs Google JPMorgan LinkedIn Microsoft Нутаниx Nvidia Oracle PayPal Пардохт Salesforce Samsung ServiceNow Tencent Tesla TripAdvisor гоҳ-гоҳ кашидан Uber Visa VMware Озмоишгоҳҳои Walmart Yahoo Yandex Зилов Зулилӣ
тартиботи ҳарбӣ Ҷустуҷӯи бинарӣ

Массиви ҷудошударо дида мебароем, аммо як нишондиҳанда интихоб карда шуд ва дар он лаҳза чархзанӣ карда шуд. Ҳоло, пас аз гардиши массив, аз шумо талаб карда мешавад, ки унсури муайяни ҳадафро ёбед ва индекси онро баргардонед. Дар ҳолате, ки элемент мавҷуд нест, баргардонед -1. Мушкилот одатан ҳамчун Ҷустуҷӯ дар ҳалли массиви гардишёфтаи Leetcode номида мешавад. Пас, дар савол ба мо массиви баъзе унсурҳои бутун дода мешавад, ки дар индекси муайяне, ки барои мо маълум нест, мураттаб ва гардонида мешаванд. Дар баробари массив, ба мо инчунин як унсури мушаххас дода мешавад, ки мо бояд онро ёбем.

Ҷустуҷӯ дар ҳалли массиви гардонидашудаи 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро дар ҳолати бадтарин, унсури ҳадаф метавонад дар охири массив бошад. Ҳамин тариқ, мураккабии вақт хатӣ аст.

Мураккабии фазо

О (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 (log N), зеро мо ҷустуҷӯи бинариро барои ёфтани унсури мақсаднок истифода кардем. Мураккабии вақт логарифм аст.

Мураккабии фазо

О (1), азбаски мо танҳо шумораи муайяни элементҳоро нигоҳ медоштем, мураккабии фазо доимист.