חפש בפתרון Leetcode ממוינת ממוינת


רמת קושי בינוני
נשאל לעתים קרובות Adobe Alibaba אמזון בעברית תפוח עץ בלומברג Byte סיסקו eBay Expedia פייסבוק גולדמן זאקס Google פי מורגן לינקדין מיקרוסופט נוטניקס Nvidia אורקל פייפאל Paytm Salesforce סמסונג ServiceNow Tencent טסלה TripAdvisor פִּרפּוּר סופר וִיזָה VMware מעבדות וולמארט יאהו Yandex Zillow זולילי
מערך חיפוש בינארי

שקול מערך ממוין אך אינדקס אחד נבחר והמערך הסתובב בנקודה זו. כעת, לאחר שסובב המערך אתה נדרש למצוא אלמנט יעד מסוים ולהחזיר את האינדקס שלו. במקרה שהאלמנט לא קיים, החזר -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 (N) מכיוון שבמקרה הגרוע ביותר, אלמנט היעד עשוי להיות קיים בסוף המערך. לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

O (1)מאחר ואין לנו מידע לגבי כל אלמנט ספציפי והשתמשנו במספר קבוע של משתנים. כך מורכבות החלל קבועה.

גישה אופטימלית לחיפוש במערך ממוין מסובב

הגישה שהוזכרה קודם לא השתמשה בעובדה שהמערך היה מערך ממוין מסובב. לכן, בגישה זו, אנו מנסים להשתמש בעובדה זו כדי להפחית את מורכבות הזמן. שקול, אם היה לנו מערך מסודר, היינו פשוט משתמשים חיפוש בינארי אבל למקרה שזה קצת מסובך. גם כאן אנו נדרשים להשתמש בחיפוש בינארי. אך אם אנו משתמשים בחיפוש בינארי, כיצד נדע באיזה חלק של המערך לבחור ברגע שנמצא באלמנט האמצעי של המערך? מכיוון שאנחנו לא יכולים פשוט לעקוב אחר אלגוריתם החיפוש הבינארי המקורי מכיוון שמדובר במערך ממוין מסובב. אז יש שינוי קל בחיפוש הבינארי הרגיל.

לכן, בדרך כלל בחיפוש בינארי, אנו בודקים אם האלמנט הנוכחי (אלמנט במרכז האינדקס) זהה ליעד, ואז נחזיר את האינדקס שלו. שלב זה נשאר כאן. מלבד זאת, אם הם אינם זהים, אנו בודקים אם הציר מונח מימין [לאלמנט הנוכחי או משמאל. אם הוא שוכן ימינה, אנו בודקים אם היעד נמצא במערך משנה שאינו מסובב, אם זה אנו מעדכנים את הגבוה אחר אנו מעדכנים את הנמוך. באופן דומה, אם הציר מונח שמאלה, שוב נבדוק אם המטרה נמצאת במערך המשנה שאינו מסובב, אנו מעדכנים את הנמוך, אחרת אנו מעדכנים את הגבוה. ובסופו של דבר, אם אנו יוצאים מהלולאה, אנו בטוחים שהמטרה אינה קיימת במערך הנתון.

קוד אופטימיזציה לחיפוש בפתרון Array 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

קוד ג'אווה

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), מכיוון שאחסנו רק מספר קבוע כלשהו של אלמנטים, מורכבות החלל קבועה.