اولین و آخرین موقعیت عنصر را در محلول آرایه مرتب شده پیدا کنید


سطح دشواری متوسط
اغلب در آمازون بلومبرگ ByteDance فیس بوک گوگل مایکروسافت وحی حال بارگذاری
صف LeetCode

بیان مسأله

در این مقاله با عنوان "پیدا کردن اولین و آخرین موقعیت عنصر در مرتب سازی مرتب شده در راه حل کد" ، ما در مورد راه حل مسئله کد کد بحث خواهیم کرد. در مسئله داده شده یک آرایه به ما داده می شود. همچنین یک عنصر هدف به ما داده می شود. عناصر آرایه با افزایش ترتیب توالی می شوند.

ما باید اولین و آخرین موقعیت عنصر هدف را در آرایه مرتب سازی شده پیدا کنیم.

اگر عنصر هدف وجود نداشته باشد ، [-1 ، -1] را برگردانید.

مثال

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

شرح:

اولین و آخرین موقعیت عنصر را در محلول آرایه مرتب شده پیدا کنید

مانند آرایه مرتب شده داده شده ، 5 برای اولین بار در شاخص شماره 2 و آخرین بار در شاخص شماره 4 ظاهر می شود.

روش

رویکرد ساده لوحانه برای حل این مشکل اسکن کل آرایه و بازگرداندن شاخص است که برای اولین بار و آخرین بار با هدف مواجه می شویم. پیچیدگی زمانی برای این الگوریتم O (n) است زیرا در بدترین حالت ممکن است نیاز به آرایه کامل داشته باشیم.

همانطور که عناصر به ترتیب بیشتر مرتب می شوند ، می توانیم از آن استفاده کنیم. علی رغم انجام جستجوی خطی ، از a استفاده خواهیم کرد جستجوی دودویی برای پیدا کردن اولین و آخرین وقایع عنصر هدف. این کد جستجوی دودویی کمی متفاوت با کد جستجوی دودویی معمولی است که در آن بررسی می کنیم که آیا این عنصر در آرایه مرتب شده وجود دارد یا خیر.

این تغییرات کوچک در کد جستجوی دودویی عادی است:

  1. این برنامه بلافاصله پس از یافتن عنصر مورد نظر خاتمه نمی یابد. ما حلقه را تا شروع = پایان اجرا خواهیم کرد.
  2. تغییر دیگر در نقطه ای است که arr [mid] == هدف قرار گیرد.
    1. برای پایان اولین اتفاق = اواسط 1.
    2. و برای آخرین وقوع شروع کنید = اواسط + 1.

موقعیت اول و آخرین عنصر را در محلول آرایه مرتب شده کد پیدا کنید

کد C ++

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

تحلیل پیچیدگی

پیچیدگی زمانی

پیچیدگی زمانی کد فوق است O (log (n))که n اندازه آرایه است. زیرا در حین جستجوی دودویی حداکثر در حال پردازش عناصر log (n) هستیم.

پیچیدگی فضا

پیچیدگی فضایی کد فوق است O (1) زیرا ما فقط از یک متغیر برای ذخیره پاسخ استفاده می کنیم.

منابع