پیک عنصر را پیدا کنید


سطح دشواری متوسط
اغلب در خشت آمازون سیب بلومبرگ ByteDance فیس بوک گوگل Quora ویزا
صف جستجوی دودویی تفرقه بینداز و حکومت کن جستجو

بفهمیم پیک عنصر را پیدا کنید مسئله. امروز ما با خود داریم صف که به عنصر اوج خود نیاز دارد. حالا ، شما باید این س beال را داشته باشید که منظور من از عنصر اوج چیست؟ عنصر اوج عنصری است که از همه همسایگان بزرگتر باشد.

مثال: با توجه به آرایه ای از [1,2,3,1،XNUMX،XNUMX،XNUMX]

عنصر قله: 3

اجازه دهید ما با ارائه یک تصویر بهتر آن را درک کنیم

پیک عنصر را پیدا کنید
نمایش عنصر Peak برای مثال آرایه

تصویر فوق کاملاً نشان می دهد که 4 از عناصر همسایه اش برای رسیدن به قسمت متمایز است عنصر اوج. اکنون چالشی که پیش روی ماست نحوه برخورد ما با این مسئله است.

رویکرد -1

Brute Force For Find Peak Element

مشاهده استانداردی که می توانیم از تصویر انجام دهیم ، بازگرداندن حداکثر عنصر (همان چیزی که برجسته است) در کل آرایه است.

اجازه دهید فرآیند یافتن حداکثر عنصر از آرایه را مرور کنیم

  • یک متغیر حداکثر را حفظ کنید. ابتدا مقدار را به عنوان عنصر 0 از آرایه در آن قرار دهید.
  • برای ذخیره شاخص ، یک متغیر را حفظ کنید. در اینجا ، ج
  • یک حلقه را در کل آرایه اجرا کنید
    • هر بار با مقداری بیشتر از حداکثر مواجه می شویم
      • متغیر حداکثر را به روز کنید
      • مقدار جدید شاخص را در j قرار دهید
  • بازگشت j

کد ++ C برای یافتن عنصر اوج

class Solution 
{
public:
    int findPeakElement(vector<int>& nums) 
    {
     int max=nums[0];
     int pos=0;
     for(int i=0;i<nums.size();i++)
     {
      if(max<nums[i]) 
      {
          max=nums[i];
          pos=i;
      }
     }
    return pos;    
    }
};
7
1 3 8 2 1 5 3
2

کد جاوا برای یافتن عنصر Peak

class Solution 
{
    public int findPeakElement(int[] nums) 
    {
     int max=nums[0];
     int pos=0;
     for(int i=0;i<nums.length;i++)
     {
      if(max<nums[i]) 
      {
          max=nums[i];
          pos=i;
      }
     }
    return pos;
    }
}
5
-10 1 0 10 5
3

پیچیدگی زمان رویکرد = O (n)

ما در دوره ای زندگی می کنیم که می توان همه چیز را سریعتر ساخت. بنابراین ، چرا این راه حل نیست؟

بگذارید آن را از بالا برداریم و آن را O (log n) کنیم

رویکرد -2

جستجو بین

اکنون که ابزارهای خطی خود را به پایان رساندیم ، اجازه دهید ما به تصویر بقیه مادر ورود همه چیز را وارد کنیم (n).

اینجا چکار کنیم؟

  • دو نشانگر را بالا و پایین نگه دارید
  • با استفاده از اشاره گرها ، نقطه میانی را محاسبه کنید
    • هر بار عنصر وسط از عنصر مجاور آن بزرگتر است
      • ما در نیمه اول آرایه شروع به جستجوی عنصری می کنیم که ممکن است بیشتر باشد
      • چرا؟
        • نیمه دوم قطعاً اوج خود را به نیمه اول تحویل داده و به قانون بزرگتر بودن ما خیانت کرده است
    • هر بار عنصر وسط از عنصر مجاور آن کوچکتر می شود
      • ما در نیمه دوم آرایه شروع به جستجوی عنصری می کنیم که ممکن است بیشتر از همسایگان باشد
      • چرا؟
        • نیمه اول قطعاً اوج خود را به نیمه دوم تحویل داده و به قانون بزرگتر بودن ما خیانت کرده است
    • مرتباً آن را تکرار کنید تا کمترین مقدار آن از مقدار زیاد بیشتر شود
    • عنصر را در حالت پایین قرار دهید همانطور که از آن تشکیل شده است اوج عنصر 

کد جاوا

class Solution 
{
    public int findPeakElement(int[] nums) 
    {
    int low=0;
     int hig=nums.length-1;
     while(hig>low)
     {
         int mid=low+(hig-low)/2;
         if(nums[mid]>nums[mid+1])
             hig=mid;
         else
             low=mid+1;
     }
     return low;    
    }
}
5
10 11 0 10 5
1

کد ++ C

class Solution 
{
    public:
    int findPeakElement(vector<int>& nums) 
    {
     int low=0;
     int hig=nums.size()-1;
     while(hig>low)
     {
         int mid=low+(hig-low)/2;
         if(nums[mid]>nums[mid+1])
             hig=mid;
         else
             low=mid+1;
     }
     return low;    
    }
};
5
0 1 0 14 5
1

La پیچیدگی زمانی رویکرد فوق = O (ورود به سیستم)

پیچیدگی فضا = O (1)

منابع

یادگیری را متوقف نکنید و یکی از جالب ترین تکنیک های مرتب سازی را درگیر ما کنید:

درج مرتب سازی