રોટેટેડ સ Sર્ટ થયેલ એરે લીટકોડ સોલ્યુશનમાં શોધો  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ છોકરાઓ એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance સિસ્કો ઇબે એક્સપેડિયા ફેસબુક ગોલ્ડમૅન સૅશ Google જેપીમોર્ગન LinkedIn માઈક્રોસોફ્ટ ન્યુટનિક્સ Nvidia ઓરેકલ પેપાલ પેટીએમ Salesforce સેમસંગ સેવા હવે Tencent ટેસ્લા TripAdvisor twitch ઉબેર વિઝા વીએમવેર વોલમાર્ટ લેબ્સ યાહૂ યાન્ડેક્ષ ઝિલો ઝુલ્લી
ગાણિતીક નિયમો અરે દ્વિસંગી શોધ કોડિંગ મુલાકાત ઇન્ટરવ્યુની તૈયારી લેટકોડ LeetCodeSolutions

એક સ .ર્ટ થયેલ એરે ધ્યાનમાં લો પરંતુ એક અનુક્રમણિકા લેવામાં આવી હતી અને એરે તે સમયે ફેરવવામાં આવી હતી. હવે, એકવાર એરે ફેરવ્યા પછી તમારે કોઈ વિશિષ્ટ લક્ષ્ય તત્વ શોધવા અને તેની અનુક્રમણિકા પરત કરવાની જરૂર છે. કિસ્સામાં, તત્વ હાજર નથી, વળતર -1. સમસ્યાને સામાન્ય રીતે સર્ચ ઇન રોટેટેડ સortedર્ટ્ડ એરે લીટકોડ સોલ્યુશન તરીકે ઓળખવામાં આવે છે. તેથી પ્રશ્નમાં, અમને કેટલાક પૂર્ણાંક તત્વોની એરે પ્રદાન કરવામાં આવી છે જે આપણને ખબર નથી તે ચોક્કસ અનુક્રમણિકા પર સ .ર્ટ અને ફેરવવામાં આવે છે. એરે સાથે, અમને એક વિશિષ્ટ તત્વ પણ આપવામાં આવ્યું છે જે આપણને શોધવાની જરૂર છે.

રોટેટેડ સ Sર્ટ થયેલ એરે લીટકોડ સોલ્યુશનમાં શોધોપિન

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

સમજૂતી: તલાશી લેવાનું તત્વ is છે. તત્વ સૂચકાંક 4 પર જોવા મળે છે, તેથી અમે લક્ષ્યની અનુક્રમણિકા પરત કરીએ છીએ.

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

સમજૂતી: તત્વ એરેમાં હાજર ન હોવાથી, આપણે પાછા વળ્યા છીએ -1.

રોટેટેડ સortedર્ટ થયેલ એરેમાં શોધ માટે બ્રુટ ફોર્સ અભિગમ  

સમસ્યા "રોટેટેડ સortedર્ટ થયેલ એરેમાં શોધ કરો" આપેલ રોટેટેડ સortedર્ટ થયેલ એરેમાં લક્ષ્ય તત્વની અનુક્રમણિકા શોધવા માટે પૂછે છે. અને આપણે પહેલેથી જ ચર્ચા કરી છે કે ફેરવાયેલ સortedર્ટ થયેલ એરે શું છે? તેથી, સૌથી સરળ પદ્ધતિ કે જેના વિશે કોઈ વિચારી શકે છે તે છે રેખીય શોધનો પ્રયાસ કરવો. રેખીય શોધમાં, અમે ફક્ત આપેલને વટાવીએ છીએ એરે અને તપાસો કે શું વર્તમાન તત્વ આપણું લક્ષ્ય તત્વ છે. જો વર્તમાન તત્વ લક્ષ્ય તત્વ હોય તો અમે વર્તમાન અનુક્રમણિકા પાછા કરીએ છીએ નહીં તો આપણે પાછા ફરો .1. અભિગમ ખૂબ જ સરળ છે પરંતુ તે એ હકીકતનો ઉપયોગ કરતું નથી કે એરે સ indexર્ટ કરે છે અને એક જ ઇન્ડેક્સ પર ફેરવવામાં આવે છે. આ અભિગમમાં રેખીય સમયની જટિલતા છે.

આ પણ જુઓ
એન-થ્રી ટ્રિબોનાકી નંબર લેટકોડ સોલ્યુશન

રોટેટેડ સortedર્ટ થયેલ એરે લીટકોડ સોલ્યુશનમાં શોધ માટેનો કોડ

સી ++ કોડ

#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);
}

જાવા કોડ

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));
    }
}

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે સૌથી ખરાબ કિસ્સામાં, લક્ષ્ય તત્વ એરેના અંતમાં હાજર હોઈ શકે છે. આમ સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (1), કારણ કે આપણે દરેક તત્વ વિશે વિશિષ્ટ રીતે કોઈ માહિતી નથી અને સતત સંખ્યાબંધ ચલોનો ઉપયોગ કર્યો છે. આમ જગ્યા જટિલતા સતત છે.

રોટેટેડ સortedર્ટ થયેલ એરેમાં શોધ માટે Opપ્ટિમાઇઝ અભિગમ  

અગાઉ ઉલ્લેખિત અભિગમમાં એ હકીકતનો ઉપયોગ થયો નથી કે એરે એક ફેરવાયેલ સortedર્ટ થયેલ એરે હતો. તેથી, આ અભિગમમાં, અમે સમયની જટિલતાને ઘટાડવા માટે આ હકીકતનો ઉપયોગ કરવાનો પ્રયાસ કરીએ છીએ. ધ્યાનમાં લો, જો અમારી પાસે સortedર્ટ કરેલી એરે હોત, તો અમે સરળતાથી ઉપયોગ કરી શક્યા હોત દ્વિસંગી શોધ પરંતુ કિસ્સામાં આ થોડી મુશ્કેલ છે. અહીં પણ અમારે દ્વિસંગી શોધનો ઉપયોગ કરવો જરૂરી છે. પરંતુ જો આપણે દ્વિસંગી શોધનો ઉપયોગ કરીએ છીએ, તો આપણે એરેના મધ્યમ તત્વ પર આવી ગયા પછી એરેના કયા ભાગને પસંદ કરવા તે આપણે કેવી રીતે જાણી શકીએ? કારણ કે આપણે ફક્ત મૂળ દ્વિસંગી શોધ એલ્ગોરિધમનું પાલન કરી શકતા નથી કારણ કે આ એક ફેરવાયેલ સortedર્ટ થયેલ એરે છે. તેથી, સામાન્ય દ્વિસંગી શોધમાં થોડો ફેરફાર છે.

તેથી, સામાન્ય રીતે દ્વિસંગી શોધમાં, અમે તપાસીએ છીએ કે વર્તમાન તત્વ (મધ્યમ અનુક્રમણિકામાં તત્વ) લક્ષ્ય જેટલું જ છે કે નહીં, તો પછી અમે તેનું અનુક્રમણિકા પાછું આપીએ છીએ. આ પગલું અહીં સમાન રહે છે. તે સિવાય, જો તે સમાન ન હોય તો, અમે તપાસ કરીએ છીએ કે પીવટ જમણી બાજુએ છે [વર્તમાન તત્વની અથવા ડાબી બાજુએ). જો તે જમણી બાજુએ આવેલું છે, તો પછી અમે તપાસો કે લક્ષ્ય નોન-રોટેટેડ સબઅરેરેમાં છે કે કેમ, જો તે theંચાને અપડેટ કરે છે તો અમે નીચાને અપડેટ કરીએ છીએ. એ જ રીતે, જો પીવટ ડાબી બાજુ આવેલું હોય, તો ફરી તપાસ કરીએ કે લક્ષ્ય નોન-રોટેટેડ સબમરીમાં છે કે નહીં, અમે નીચાને અપડેટ કરીએ, નહીં તો અમે ઉચ્ચને અપડેટ કરીએ છીએ. અને અંતે, જો આપણે લૂપમાંથી બહાર આવીએ, તો અમને ખાતરી છે કે આપેલ એરેમાં લક્ષ્ય હાજર નથી.

આ પણ જુઓ
ચોરસ (x) લીટકોડ સોલ્યુશન

રોટેટેડ સortedર્ટ થયેલ એરે લીટકોડ સોલ્યુશનમાં શોધ માટે timપ્ટિમાઇઝ કોડ

સી ++ કોડ

#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);
}

જાવા કોડ

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));
    }
}

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (લોગ એન), કારણ કે અમે લક્ષ્ય તત્વ શોધવા માટે દ્વિસંગી શોધનો ઉપયોગ કર્યો છે. સમયની જટિલતા લોગરીધમિક છે.

આ પણ જુઓ
કોઈપણ બે તત્વો વચ્ચે ન્યૂનતમ તફાવત શોધો

અવકાશ જટિલતા

ઓ (1), કારણ કે અમે ફક્ત કેટલાક સ્થિર તત્વોની સંખ્યા સંગ્રહિત કરી છે, જગ્યા જટિલતા સતત છે.