সাজানো অ্যারে লেটকোড সমাধানে এলিমেন্টের প্রথম এবং শেষ অবস্থান সন্ধান করুন


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ব্লুমবার্গ ByteDance ফেসবুক গুগল মাইক্রোসফট আকাশবাণী উবার
বিন্যাস লেটকোড

সমস্যা বিবৃতি

"সাজানো অ্যারে লেটকোড সমাধানে উপাদানটির প্রথম এবং শেষ অবস্থান সন্ধান করুন" শিরোনামে এই নিবন্ধে আমরা একটি লেটকোড সমস্যার সমাধান নিয়ে আলোচনা করব। প্রদত্ত সমস্যায় আমাদের একটি অ্যারে দেওয়া হয়। আমাদের একটি লক্ষ্য উপাদানও দেওয়া হয়। অ্যারেতে উপাদানগুলি ক্রমবর্ধমান ক্রমে ক্রমযুক্ত হয়।

বাছাই করা অ্যারেতে আমাদের লক্ষ্য উপাদানটির প্রথম এবং শেষ অবস্থানটি সন্ধান করতে হবে।

যদি লক্ষ্য উপাদান উপস্থিত না থাকে তবে [-1, -1] ফিরে আসুন।

উদাহরণ

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

ব্যাখ্যা:

সাজানো অ্যারে লেটকোড সমাধানে এলিমেন্টের প্রথম এবং শেষ অবস্থান সন্ধান করুন

প্রদত্ত বাছাই করা অ্যারে হিসাবে 5 টি প্রথমবারের মতো 2 নম্বর সূচকে এবং শেষ বারের সূচক 4 নম্বরে প্রদর্শিত হবে।

অভিগমন

এই সমস্যাটি সমাধানের নিখুঁত দৃষ্টিভঙ্গি হ'ল পুরো অ্যারেটি স্ক্যান করে সূচকটি ফিরে আসা যখন আমরা প্রথমবার এবং শেষবারের জন্য লক্ষ্যটির মুখোমুখি হই। এই অ্যালগরিদমের সময় জটিলতা হ'ল ও (এন) হিসাবে সবচেয়ে খারাপ ক্ষেত্রে আমাদের সম্পূর্ণ অ্যারেটি অতিক্রম করতে হতে পারে।

উপাদানগুলি ক্রমবর্ধমান ক্রমে সাজানো হওয়ায় আমরা এর সুবিধা নিতে পারি। লিনিয়ার অনুসন্ধান করা সত্ত্বেও, আমরা একটি ব্যবহার করব বাইনারি অনুসন্ধান লক্ষ্য উপাদানটির প্রথম এবং শেষ ঘটনাগুলি সন্ধান করতে। এই বাইনারি অনুসন্ধান কোডটি সাধারণ বাইনারি অনুসন্ধান কোডের থেকে কিছুটা আলাদা হবে যেখানে আমরা উপাদানটি সাজানো অ্যারেতে উপস্থিত কিনা তা পরীক্ষা করে দেখি।

এগুলি সাধারণ বাইনারি অনুসন্ধান কোডের ছোট পরিবর্তনগুলি:

  1. প্রোগ্রামটি লক্ষ্য উপাদানটি খুঁজে পাওয়ার সাথে সাথেই শেষ হবে না। আমরা শুরু = শেষ অবধি লুপটি চালাব।
  2. আর একটি পরিবর্তন হল সেই বিন্দুতে যেখানে আরার [মাঝারি] == লক্ষ্য।
    1. প্রথম ঘটনার জন্য শেষ = মধ্য -1।
    2. এবং শেষ ঘটনাটির জন্য = মধ্য + 1 শুরু।

সাজানো অ্যারে লেটকোড সমাধানে উপাদানটির প্রথম এবং শেষ অবস্থান কোড সন্ধান করে

সি ++ কোড

#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]

জটিলতা বিশ্লেষণ

সময়ের জটিলতা

উপরের কোডটির সময় জটিলতা ও (লগ (এন))যেখানে এন অ্যারের আকার। কারণ আমরা বাইনারি অনুসন্ধানের সময় সর্বাধিক লগ (এন) উপাদানগুলিতে প্রক্রিয়াজাত করছি।

স্থান জটিলতা

উপরের কোডটির স্পেস জটিলতা ও (1) কারণ আমরা উত্তর সংরক্ষণের জন্য কেবল একটি পরিবর্তনশীল ব্যবহার করছি।

তথ্যসূত্র