ابحث في حل Leetcode Array Array


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي علي بابا أمازون أجهزة آبل بلومبرغ ByteDance سيسكو يباي اكسبيديا Facebook جولدمان ساكس جوجل جي بي مورغان لينكد إن: Microsoft Nutanix NVIDIA أوراكل Paypal Paytm ساليسفورسي سامسونج الخدمة الآن تينسنت تسلا على TripAdvisor نشل اوبر تأشيرة في إم وير مختبرات وول مارت ياهو ياندكس Zillow Zulily
مجموعة بحث ثنائي

ضع في اعتبارك مصفوفة مرتبة ولكن تم اختيار فهرس واحد وتم تدوير المصفوفة في تلك المرحلة. الآن ، بمجرد تدوير المصفوفة ، يُطلب منك العثور على عنصر هدف معين وإرجاع فهرسها. في حالة عدم وجود العنصر ، قم بإرجاع -1. يشار إلى المشكلة عمومًا باسم Search in Rotated Sorted Array Leetcode Solution. لذلك في السؤال ، تم تزويدنا بمصفوفة من بعض العناصر الصحيحة التي تم فرزها وتدويرها عند فهرس معين غير معروف لنا. إلى جانب المصفوفة ، لدينا أيضًا عنصر محدد علينا إيجاده.

ابحث في حل Leetcode Array Array

array: [4,5,6,7,0,1,2]
target: 4
0

توضيح: بما أن العنصر المراد البحث عنه هو 4. العنصر موجود في الفهرس 0 ، فإننا نعيد فهرس الهدف.

array: [4,5,6,7,0,1,2]
target: 3
-1

Explanation: بما أن العنصر غير موجود في المصفوفة ، فإننا نعيد -1.

نهج القوة الغاشمة للبحث في مصفوفة مرتبة مستديرة

تطلب منا مشكلة "Search in Rotated Sorted Array" إيجاد فهرس العنصر الهدف في المصفوفة التي تم فرزها والتي تم تدويرها. وقد ناقشنا بالفعل ما هي المصفوفة المستديرة المرتبة؟ لذلك ، فإن أبسط طريقة يمكن للمرء أن يفكر فيها هي تجربة البحث الخطي. في البحث الخطي ، نقوم ببساطة باجتياز المعطى مجموعة وتحقق مما إذا كان العنصر الحالي هو العنصر المستهدف لدينا. إذا كان العنصر الحالي هو العنصر الهدف فإننا نعيد الفهرس الحالي وإلا فإننا نرجع -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

كود جافا

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

كود جافا

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) ، منذ أن استخدمنا البحث الثنائي للعثور على العنصر الهدف. تعقيد الوقت لوغاريتمي.

تعقيد الفضاء

يا (1) ، نظرًا لأننا قمنا بتخزين عدد ثابت من العناصر فقط ، فإن تعقيد الفضاء ثابت.