گھمندڙ ترتيب وارين ارٽ ليٽ ڪوڊ حل ۾ ڳولھيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ ايڊوب علي بابا Amazon ايپل Bloomberg ByteDance Cisco eBay Expedia ڪريو Goldman سيچ گوگل JPMorgan LinkedIn، Microsoft جي نٿانڪس Nvidia Oracle PayPal پيٽرم Salesforce، سنگ سروس Tencent Tesla TripAdvisor Twitch سليمان وساڻ ويزا VMware والارٽ ليبز ياهو ياندڪس Zillow زليلي
ڪيريو بائنري ڳولا

ترتيب واري ترتيب تي غور ڪريو ، پر هڪ انڊيڪس چونڊيو ويو ۽ ان جڳهه تي لڳل گردش ڪئي وئي. هاڻي ، هڪ دفعو جڏهن گردش گردش ڪئي وئي آهي توهان کي گهربل هڪ خاص هدف عنصر ڳولڻ ۽ ان جو انڊيڪس واپس آڻڻ جي ضرورت آهي. صورت ۾ ، عنصر موجود ناهي ، واپسي -1. مسئلو عام طور تي روٽيڊ سٿٽڊ آري ليٽ ڪوڊ حل ۾ تلاش جي طور تي ٻڌايو ويندو آهي. تنهنڪري سوال ۾ ، اسان کي ڪجهه انگ اکر جي قطار سان مهيا ڪئي وئي آهي جيڪي هڪ خاص انڊيڪس ۾ ترتيب ۽ گردش ڪيل آهن جيڪي اسان کي نٿا isاڻن. صف سان گڏ ، اسان کي پڻ هڪ مخصوص عنصر ڏنو ويو آهي جنهن کي اسان کي ڳولڻ گهرجي.

گھمندڙ ترتيب وارين ارٽ ليٽ ڪوڊ حل ۾ ڳولھيو

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. اچڻ بلڪل سادو آهي ، پر انهي کان اها حقيقت استعمال نٿو ڪري ته صف هڪ انڊيڪس تي ترتيب ۽ گردش ڪئي وئي آهي. ھن طريقي سان لڪير وقت پيچيدگي آھي.

گردش ٿيل ترتيب وارين قطارن ۾ ڳولڻ لاءِ ڪوڊ

سي ++ ڪوڊ

#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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، ڇاڪاڻ ته بدترين صورت ۾ ، ٽارگيٽ عنصر شايد صف جي آخر ۾ موجود هوندو. ان ڪري وقت جي پيچيدگي سڌي آهي.

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

اي (1)اسان وٽ هر عنصر خاص طور تي informationاڻ ناهي ۽ متغير جي مسلسل تعداد استعمال ڪئي آهي. اھڙيءَ طرح خلائي پيچيدگي مستقل آھي.

گردش ٿيل ترتيب وارين قطارن ۾ تلاش لاءِ اصلاح جو طريقو

اچڻ کان اڳ جو نقشو بيان ڪيل حقيقت استعمال نه ڪيو آهي ته صف هڪ گردش ٿيل ترتيب واري صف هئي. تنهن ڪري ، هن طريقي سان ، اسان هن حقيقت کي استعمال ڪرڻ جي ڪوشش ڪندا آهيون وقت جي پيچيدگي کي گهٽائڻ جي. غور ڪريو ، جيڪڏهن اسان وٽ ترتيب ڏنل ترتيب هجي ، اسان بس استعمال ڪري ها بائنري ڳولا پر صورت ۾ اهو ٿورو مشڪل آهي. هتي پڻ اسان کي بائنري سرچ استعمال ڪرڻ جي گهرج آهي. پر جيڪڏهن اسان بائنري ڳولا استعمال ڪريون ٿا ، اسان ڪئين getاڻون ٿا ته هڪڙو ڀيرو جڏهن اسان صف جي وچ واري عنصر تي چونڊڻ لاءِ چونڊيندا آهيون؟ ڇاڪاڻ ته اسان صرف اصلي بائنري سرچ الورجيٿم جي پيروي نٿا ڪري سگھون ڇاڪاڻ ته اها هڪ گھٽي ٿيل ترتيب وار صف آهي. تنهن ڪري ، عام بائنري ڳولا مٿان ٿورڙي ترميم آهي.

تنهن ڪري ، عام طور تي بائنري ڳولا ۾ ، اسين چڪاس ڪريون ٿا ته ڇا موجوده عنصر (وچ انڊيڪس جو عنصر) ٽارگيٽ وانگر ساڳيو آهي ، پوءِ اسان ان جو انڊيڪس موٽايو. اهو قدم هتي ساڳيو ئي رهي ٿو. انهي کان سواء ، جيڪڏهن اهي ساڳيا نه آهن ، اسان چيڪ ڪنديون ته پيوڙو موجوده [عنصر يا بائیں کي] سا toي طرف ڪوڙ آهي. جيڪڏھن اھو صحيح تي ڪوڙ آھي ، پوءِ اسان چيڪ ڪريو ته ھدف غير گردش ٿيل سبجي ۾ ڪو آھي ، جيڪڏھن اھو وڌيڪ اپڊيٽ ڪيو ته اسان وڌيڪ کي اپڊيٽ ڪيو. ساڳي طرح ، جيڪڏهن پٻو کاٻي پاسي ڪوڙ هوندو آهي ، ٻيهر اسين جانچون ٿا ته ڇا ٽارگيٽ غير گھمڻ واري سبار ۾ ويٺو آهي ، اسان گهٽ کي اپ ڊيٽ ڪيو ، ٻي صورت ۾ اسان اون کي اپڊيٽ ڪيو. ۽ آخر ۾ ، جيڪڏهن اسان لپ مان نڪرندا آهيون ، اسان کي پڪ آهي ته ٽارگيٽ ڏنل صف ۾ موجود ناهي.

گردش ٿيل ترتيب وارين قطارن ۾ حل لاءِ اصلاح جو ڪوڊ

سي ++ ڪوڊ

#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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (لاگ اين) ، جڏهن کان اسان حدف عنصر ڳولڻ لاءِ بائنري ڳولا استعمال ڪئي آهي. وقت جي پيچيدگاري منطقي آهي.

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

اي (1) ، ڇاڪاڻ ته اسان عناصر جي صرف ڪجهه انگ اکر گڏ ڪيا آهيون ، خلائي پيچيدگي مستقل آهي.