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


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન બ્લૂમબર્ગ ByteDance ફેસબુક Google માઈક્રોસોફ્ટ ઓરેકલ ઉબેર
અરે લેટકોડ

સમસ્યા નિવેદન

"સ Sર્ટ થયેલ એરે લીટકોડ સોલ્યુશનમાં તત્વોની પ્રથમ અને છેલ્લી સ્થિતિ શોધો" શીર્ષકવાળા આ લેખમાં, અમે લીટકોડ સમસ્યાના સમાધાન વિશે ચર્ચા કરીશું. આપેલ સમસ્યામાં આપણને એરે આપવામાં આવે છે. અમને લક્ષ્ય તત્વ પણ આપવામાં આવે છે. એરેમાં તત્વો વધતા ક્રમમાં ક્રમમાં આવે છે.

આપણે સ theર્ટ થયેલ એરેમાં લક્ષ્ય તત્વની પ્રથમ અને છેલ્લી સ્થિતિ શોધવાની જરૂર છે.

જો લક્ષ્ય તત્વ હાજર ન હોય તો પાછા ફરો [-1, -1].

ઉદાહરણ

array: [1,2,5,5,5,9] , target=5
[2,4]

સમજૂતી:

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

આપેલ સોર્ટ કરેલ એરેની જેમ, 5 પ્રથમ વખત અનુક્રમણિકા નંબર 2 પર અને છેલ્લી વખત અનુક્રમણિકા નંબર 4 પર દેખાય છે.

અભિગમ

આ સમસ્યાનું નિરાકરણ લાવવાનો નિષ્ક્રીય અભિગમ એ છે કે જ્યારે પ્રથમ વખત અને છેલ્લી વાર લક્ષ્ય મળે ત્યારે આખા એરેને સ્કેન કરીને અનુક્રમણિકા પરત કરવી. આ અલ્ગોરિધમનો સમય જટિલતા એ (એન) છે કારણ કે સૌથી ખરાબ કિસ્સામાં આપણે સંપૂર્ણ એરેને પસાર કરવાની જરૂર પડી શકે છે.

જેમ જેમ તત્વોને વધતા ક્રમમાં ગોઠવવામાં આવે છે, અમે તેનો લાભ લઈ શકીએ છીએ. રેખીય શોધ કરવા છતાં, અમે એક વાપરીશું દ્વિસંગી શોધ લક્ષ્ય તત્વની પ્રથમ અને અંતિમ ઘટનાઓ શોધવા માટે. આ દ્વિસંગી શોધ કોડ સામાન્ય બાઈનરી શોધ કોડથી થોડો અલગ હશે જ્યાં અમે તપાસો કે તત્વ સ theર્ટ થયેલ એરેમાં છે કે નહીં.

સામાન્ય બાઈનરી શોધ કોડમાં આ નાના ફેરફારો છે:

  1. પ્રોગ્રામ લક્ષ્ય તત્વ શોધવા પછી તરત જ સમાપ્ત થશે નહીં. આપણે શરૂ = અંત સુધી લૂપ ચલાવીશું.
  2. બીજો ફેરફાર એ બિંદુએ છે જ્યાં એઆરઆર [મધ્ય] == લક્ષ્ય.
    1. પ્રથમ ઘટના માટે અંત = મધ્ય -1.
    2. અને છેલ્લી ઘટના માટે પ્રારંભ = મધ્ય + 1.

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

સી ++ કોડ

#include <bits/stdc++.h> 
using namespace std; 
    int findFirst(vector<int>& nums, int target)
    {
         int ans = -1;
    int s = 0;
    int e = nums.size() - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            e = mid - 1;
        }
    }
    return ans;
    }
     int findLast(vector<int>& nums, int target)
    {
          int ans = -1;
    int s = 0;
    int e = nums.size() - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            s = mid + 1;
        }
    }
    return ans;
    }
    vector<int> find(vector<int>& nums, int target) {
        vector<int>result(2);
         result[0] = findFirst(nums, target);
         result[1] = findLast(nums, target);
         return result;
    }

int main() 
{ 
 vector<int> arr = {1,2,5,5,5,9}; 
int target=5;
vector<int> ans(2);
ans=  find(arr,target);
for(int i=0;i<2;i++)
 cout<<ans[i]<<" "; 
 return 0;
}
[2,4]

જાવા કોડ

import java.util.Arrays; 
public class Tutorialcup {
    public static int[] find(int[] nums, int target) {
    int[] result = new int[2];
    result[0] = findFirst(nums, target);
    result[1] = findLast(nums, target);
    return result;
}

private static int findFirst(int[] nums, int target){
    int ans = -1;
    int s = 0;
    int e = nums.length - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            e = mid - 1;
        }
    }
    return ans;
}
    

private static int findLast(int[] nums, int target){
       int ans = -1;
    int s = 0;
    int e = nums.length - 1;
    while(s <= e){
        int mid =s+ (e-s) / 2;
        if (nums[mid] < target) 
            s = mid + 1;
        else if (nums[mid] > target) 
            e = mid - 1;
        else  {
            ans = mid;
            s = mid + 1;
        }
    }
    return ans;
}
  public static void main(String[] args) {
    int [] arr = {1,2,5,5,5,9}; 
    int target=5;
     int[] ans = new int[2];
    ans=  find(arr,target);
    System.out.println(Arrays.toString(ans));
  }
}
[2,4]

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

સમયની જટિલતા

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

જગ્યાની જટિલતા

ઉપરોક્ત કોડની અવકાશ જટિલતા છે ઓ (1) કારણ કે આપણે જવાબો સંગ્રહવા માટે માત્ર એક વેરીએબલ વાપરી રહ્યા છીએ.

સંદર્ભ