Търсете в Решение със сортиран масив Leetcode


Ниво на трудност M
Често задавани в Кирпич Alibaba Амазонка ябълка Bloomberg ByteDance Cisco иБей Expedia Facebook Goldman Sachs Google JPMorgan LinkedIn Microsoft Nutanix Nvidia Оракул PayPal Paytm Salesforce Samsung ServiceNow Tencent Tesla TripAdvisor Twitch Uber виза VMware Walmart Labs Yahoo Yandex Zillow Джули
Array Двоично търсене

Помислете за сортиран масив, но е избран един индекс и масивът е завъртян в тази точка. След като масивът е завъртян, вие трябва да намерите конкретен целеви елемент и да върнете неговия индекс. В случай, че елементът не присъства, върнете -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.

Подход на груба сила за търсене в завъртян сортиран масив

Проблемът „Търсене в завъртян сортиран масив“ ни изисква да намерим индекса на целевия елемент в дадения завъртян сортиран масив. И вече обсъдихме какво е завъртян сортиран масив? И така, най-простият метод, за който човек може да се сети, е да изпробва Линейно търсене. При линейно търсене ние просто пресичаме даденото масив и проверете дали текущият елемент е нашият целеви елемент. Ако текущият елемент е целевият елемент, ние връщаме текущия индекс, иначе връщаме -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 (1), тъй като не разполагаме с информация за всеки елемент конкретно и сме използвали постоянен брой променливи. По този начин сложността на пространството е постоянна.

Оптимизиран подход за търсене в завъртян сортиран масив

Споменатият по-рано подход не използва факта, че масивът е завъртян сортиран масив. Така че, в този подход ние се опитваме да използваме този факт, за да намалим сложността на времето. Помислете, ако имахме сортиран масив, щяхме просто да използваме двоично търсене но в случай, че това е малко сложно. Тук също се изисква да използваме двоично търсене. Но ако използваме двоично търсене, как да разберем коя част от масива да изберем, след като сме в средния елемент на масива? Тъй като не можем просто да следваме оригиналния двоичен алгоритъм за търсене, защото това е завъртян сортиран масив. И така, има леко изменение в нормалното бинарно търсене.

Така че, обикновено при двоично търсене, ние проверяваме дали текущият елемент (елемент в средата на индекса) е същият като target, тогава връщаме неговия индекс. Тази стъпка остава същата и тук. Освен това, ако те не са еднакви, ние проверяваме дали въртенето е разположено отдясно [на текущия елемент или отляво. Ако се намира вдясно, проверяваме дали целта се намира в невъртян подмасив, ако го актуализираме високия, в противен случай актуализираме ниския. По същия начин, ако пивотът лежи вляво, отново проверяваме дали целта лежи в невъртяната подрешетка, актуализираме ниската, в противен случай актуализираме високата. И в крайна сметка, ако излезем от цикъла, сме сигурни, че целта не присъства в дадения масив.

Оптимизиран код за търсене в Rotated Sorted Array Leetcode Solution

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), тъй като използвахме двоично търсене, за да намерим целевия елемент. Сложността във времето е логаритмична.

Сложност на пространството

O (1), тъй като съхранихме само някакъв постоянен брой елементи, сложността на пространството е постоянна.