Αναζήτηση στο Rotated Sorted Array Leetcode Solution


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις πλίθα Alibaba αμαζόνα μήλο Bloomberg ByteDance Cisco eBay Expedia Facebook Goldman Sachs Google JPMorgan LinkedIn Microsoft Nutanix Nvidia μαντείο PayPal Paytm Salesforce Samsung Υπηρεσία Τώρα Tencent Τέσλα Το TripAdvisor Twitch Uber Visa VMware Εργαστήρια Walmart Yahoo Yandex Zillow Ζούλι
Παράταξη Δυαδική αναζήτηση

Εξετάστε έναν ταξινομημένο πίνακα αλλά επιλέχθηκε ένα ευρετήριο και ο πίνακας περιστράφηκε σε αυτό το σημείο. Τώρα, αφού περιστραφεί ο πίνακας, πρέπει να βρείτε ένα συγκεκριμένο στοιχείο στόχου και να επιστρέψετε το ευρετήριό του. Σε περίπτωση που το στοιχείο δεν υπάρχει, επιστρέψτε -1. Το πρόβλημα αναφέρεται γενικά ως Αναζήτηση στο Rotated Sorted Array Leetcode Solution. Στην ερώτηση λοιπόν, έχουμε μια σειρά από ακέραια στοιχεία που ταξινομούνται και περιστρέφονται σε ένα συγκεκριμένο ευρετήριο που δεν είναι γνωστό σε εμάς. Μαζί με τον πίνακα, μας δίνεται επίσης ένα συγκεκριμένο στοιχείο που πρέπει να βρούμε.

Αναζήτηση στο Rotated Sorted Array Leetcode Solution

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. Η προσέγγιση είναι πολύ απλή αλλά επειδή δεν χρησιμοποιεί το γεγονός ότι ο πίνακας ταξινομείται και περιστρέφεται σε ένα μόνο ευρετήριο. Αυτή η προσέγγιση έχει γραμμική χρονική πολυπλοκότητα.

Κωδικός για αναζήτηση στο Rotated Sorted Array Leetcode Solution

Κωδικός 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), επειδή στη χειρότερη περίπτωση, το στοιχείο στόχος μπορεί να υπάρχει στο τέλος του πίνακα. Έτσι, η πολυπλοκότητα του χρόνου είναι γραμμική.

Διαστημική πολυπλοκότητα

Ο (1), δεδομένου ότι δεν έχουμε συγκεκριμένες πληροφορίες σχετικά με κάθε στοιχείο και έχουμε χρησιμοποιήσει έναν σταθερό αριθμό μεταβλητών. Έτσι, η διαστημική πολυπλοκότητα είναι σταθερή.

Βελτιστοποιημένη προσέγγιση για αναζήτηση σε περιστρεφόμενη ταξινομημένη σειρά

Η προσέγγιση που αναφέρθηκε προηγουμένως δεν χρησιμοποίησε το γεγονός ότι ο πίνακας ήταν ένας περιστρεφόμενος ταξινομημένος πίνακας. Έτσι, σε αυτήν την προσέγγιση, προσπαθούμε να χρησιμοποιήσουμε αυτό το γεγονός για να μειώσουμε την πολυπλοκότητα του χρόνου. Σκεφτείτε, εάν είχαμε ένα ταξινομημένο πίνακα, θα χρησιμοποιούσαμε απλώς δυαδική αναζήτηση αλλά σε περίπτωση που αυτό είναι λίγο δύσκολο. Εδώ απαιτείται επίσης η χρήση δυαδικής αναζήτησης. Αλλά αν χρησιμοποιούμε δυαδική αναζήτηση, πώς θα μάθουμε ποιο μέρος του πίνακα θα επιλέξουμε μόλις βρεθούμε στο μεσαίο στοιχείο του πίνακα; Επειδή δεν μπορούμε απλώς να ακολουθήσουμε τον αρχικό αλγόριθμο δυαδικής αναζήτησης, επειδή πρόκειται για έναν περιστρεφόμενο πίνακα ταξινόμησης. Λοιπόν, υπάρχει μια μικρή τροποποίηση της κανονικής δυαδικής αναζήτησης.

Έτσι, συνήθως σε μια δυαδική αναζήτηση, ελέγχουμε αν το τρέχον στοιχείο (στοιχείο στο μέσο ευρετήριο) είναι ίδιο με το στόχο και μετά επιστρέφουμε το ευρετήριό του. Αυτό το βήμα παραμένει ίδιο εδώ. Εκτός από αυτό, εάν δεν είναι ίδιοι, ελέγχουμε εάν ο άξονας βρίσκεται στα δεξιά [του τρέχοντος στοιχείου ή στα αριστερά. Εάν βρίσκεται στα δεξιά, τότε ελέγξουμε εάν ο στόχος βρίσκεται σε μη περιστρεφόμενη υποπεριοχή, εάν ενημερώνει το υψηλότερο άλλο ενημερώνουμε το χαμηλό. Ομοίως, εάν ο άξονας βρίσκεται στα αριστερά, ελέγξουμε ξανά εάν ο στόχος βρίσκεται στη μη περιστρεφόμενη υποπεριοχή, ενημερώνουμε το χαμηλό, αλλιώς ενημερώνουμε το υψηλό. Και στο τέλος, εάν βγαίνουμε από το βρόχο, είμαστε σίγουροι ότι ο στόχος δεν υπάρχει στον δεδομένο πίνακα.

Βελτιστοποιημένος κώδικας για αναζήτηση στο 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), αφού χρησιμοποιήσαμε δυαδική αναζήτηση για να βρούμε το στοιχείο στόχου. Η χρονική πολυπλοκότητα είναι λογαριθμική.

Διαστημική πολυπλοκότητα

Ο (1), δεδομένου ότι αποθηκεύσαμε μόνο έναν σταθερό αριθμό στοιχείων, η πολυπλοκότητα του χώρου είναι σταθερή.