گھمائے ہوئے ترتیب والے سرے لیٹکوڈ حل میں تلاش کریں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب Alibaba ایمیزون ایپل بلومبرگ ByteDance سسکو ای بے Expedia فیس بک گولڈمین سیکس گوگل JPMorgan لنکڈ مائیکروسافٹ نیوٹنکس NVIDIA اوریکل پے پال پی ٹی ایم ایم Salesforce سیمسنگ حاضر سروس Tencent کے Tesla TripAdvisor کی مروڑ Uber ویزا VMware والمارٹ لیبز یاہو Yandex Zillow زلیجی
لڑی ثنائی تلاش

ترتیب شدہ سرنی پر غور کریں لیکن ایک اشاریہ چن لیا گیا تھا اور اس مقام پر سرنی کو گھمایا گیا تھا۔ اب ، ایک بار سرنی گھمائے جانے کے بعد آپ کو ایک خاص ہدف عنصر تلاش کرنے اور اس کی اشاریہ کو واپس کرنے کی ضرورت ہوگی۔ ایسی صورت میں ، عنصر موجود نہیں ہے ، -1 واپس کریں۔ عام طور پر اس مسئلے کو سرچ ان گھومنے والے ترتیب والے سرے لیٹکوڈ حل کے نام سے جانا جاتا ہے۔ لہذا سوال میں ، ہمیں کچھ عدد عنصروں کی ایک صف فراہم کی جاتی ہے جو ایک مخصوص انڈیکس میں چھانٹ کر گھمایا جاتا ہے جو ہمیں معلوم نہیں ہے۔ صف کے ساتھ ساتھ ، ہمیں ایک خاص عنصر بھی دیا جاتا ہے جو ہمیں ڈھونڈنے کی ضرورت ہے۔

گھمائے ہوئے ترتیب والے سرے لیٹکوڈ حل میں تلاش کریں

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 واپس آتے ہیں۔

گھمائے گئے ترتیب والے صف میں تلاش کے لئے بروٹ فورس نقطہ نظر

مسئلہ "گھمائے ہوئے ترتیب والے سرے میں تلاش کریں" ہمیں بتائے گئے گھمائے ہوئے ترتیب والے صف میں ہدف عنصر کا اشاریہ تلاش کرنے کے لئے کہتا ہے۔ اور ہم پہلے ہی بحث کرچکے ہیں کہ گھمائے گئے ترتیب والے سرے کیا ہے؟ لہذا ، سب سے آسان طریقہ جس کے بارے میں کوئی سوچ سکتا ہے وہ ہے لکیری تلاش کی کوشش کرنا۔ لکیری تلاش میں ، ہم صرف دیئے گئے کو عبور کرتے ہیں صف اور چیک کریں کہ کیا موجودہ عنصر ہمارا ہدف عنصر ہے۔ اگر موجودہ عنصر ہدف عنصر ہے تو ہم موجودہ انڈیکس کو واپس کرتے ہیں بصورت دیگر ہم واپس آتے ہیں۔ نقطہ نظر بہت آسان ہے لیکن چونکہ یہ اس حقیقت کو استعمال نہیں کرتا ہے کہ کسی ایک انڈیکس میں سرنی کو چھانٹا اور گھمایا جاتا ہے۔ اس نقطہ نظر میں وقتی پیچیدگی ہوتی ہے۔

کوٹ برائے تلاش میں گھمائے گئے ترتیب والے سرے لیٹکوڈ حل

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) ، کیونکہ بدترین حالت میں ، ہدف عنصر سرنی کے آخر میں موجود ہوسکتا ہے۔ اس طرح وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

O (1)، چونکہ ہم خاص طور پر ہر عنصر کے بارے میں کوئی معلومات نہیں رکھتے ہیں اور متغیرات کی مستقل تعداد میں استعمال کرتے ہیں۔ اس طرح جگہ کی پیچیدگی مستقل ہے۔

گھمائے ہوئے ترتیب والے صف میں تلاش کے ل Op آپtimٹائزڈ اپروچ

پہلے بیان کردہ نقطہ نظر نے یہ حقیقت استعمال نہیں کی تھی کہ سرنی گھماؤ شدہ ترتیب شدہ صف ہے۔ لہذا ، اس نقطہ نظر میں ، ہم وقت کی پیچیدگی کو کم کرنے کے لئے اس حقیقت کو استعمال کرنے کی کوشش کرتے ہیں۔ غور کیج. ، اگر ہمارے پاس ترتیب کی صف ہوتی تو ہم آسانی سے استعمال ہوتے بائنری تلاش لیکن اگر یہ قدرے مشکل ہے۔ یہاں بھی ہمیں بائنری تلاش کرنے کی ضرورت ہے۔ لیکن اگر ہم بائنری تلاش کا استعمال کرتے ہیں تو ، ہمیں یہ کیسے معلوم ہوگا کہ ایک بار صف کے درمیانی عنصر پر آنے کے بعد سرنی کا کون سا حصہ منتخب کرنا ہے؟ کیونکہ ہم صرف بائنری تلاش کے الگورتھم کی پیروی نہیں کرسکتے ہیں کیونکہ یہ گھمایا ہوا ترتیب ہے۔ تو ، عام بائنری تلاش کے دوران معمولی ترمیم ہے۔

لہذا ، عام طور پر بائنری تلاش میں ، ہم جانچتے ہیں کہ موجودہ عنصر (وسط انڈیکس میں عنصر) ہدف کے برابر ہے ، پھر ہم اس کی اشاریہ کو لوٹاتے ہیں۔ یہ مرحلہ آج بھی وہی ہے۔ اس کے علاوہ ، اگر وہ ایک جیسے نہیں ہیں ، تو ہم چیک کرتے ہیں کہ محور دائیں طرف [موجودہ عنصر کے بائیں یا بائیں طرف ہے۔ اگر یہ دائیں طرف ہے ، تو ہم جانچ پڑتال کرتے ہیں کہ آیا ہدف غیر گھومنے والے سبریے میں ہے ، اگر ہم اعلی کو اپ ڈیٹ کرتے ہیں اور نہیں تو ہم کم کو اپ ڈیٹ کرتے ہیں۔ اسی طرح ، اگر محور بائیں طرف جھوٹ بولتا ہے ، تو پھر ہم جانچ پڑتال کرتے ہیں کہ آیا ہدف غیر گھمایا ہوا سبریے میں ہے ، ہم کم کو اپ ڈیٹ کرتے ہیں ، ورنہ ہم اونچے کو اپ ڈیٹ کرتے ہیں۔ اور آخر میں ، اگر ہم لوپ سے باہر آجائیں تو ، ہمیں یقین ہے کہ ہدف دیئے گئے صف میں موجود نہیں ہے۔

گھمائے ہوئے ترتیب والے سرے لیٹ کوڈ حل میں تلاش کے لئے آپٹیمائزڈ کوڈ

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) ، چونکہ ہم نے عناصر کی صرف کچھ مستقل تعداد کو ذخیرہ کیا ہے ، لہذا جگہ کی پیچیدگی مستقل ہے۔