Пайдо кардани унсури қулла


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon себ Блумберг ByteDance Facebook Google Quora Visa
тартиботи ҳарбӣ Ҷустуҷӯи бинарӣ Тақсим кунед ва ғолиб шавед Ҷустуҷӯ

Биё бифаҳмем Пайдо кардани унсури қулла мушкилот. Имрӯз мо бо худ ан асал ки ба унсури авҷи он ниёз дорад. Ҳоло, шумо бояд дар ҳайрат бошед, ки ман унсури авҷро дар назар дорам? Унсури қулла якеест, ки аз ҳама ҳамсояҳои худ бузургтар аст.

мисол: Бо назардошти массиви [1,2,3,1]

Унсури қуллаи: 3

Биёед инро бо тасвири тасвир беҳтар фаҳмем

Пайдо кардани унсури қулла
Намоиши унсури қулла барои массиви намуна

Тасвири дар боло овардашуда комилан нишон медиҳад, ки чӣ гуна 4 аз унсурҳои ҳамсояи худ фарқ мекунад, то онро ба унсури авҷ. Ҳозир вазифаи мо дар он аст, ки чӣ гуна ба мушкилоти додашуда муносибат кунем.

Равиш-1

Force Brute For Find Element Peak

Мушоҳидаи стандартӣ, ки мо метавонем аз тасвири он баргардонем, ин баргардонидани элементҳои максималӣ (он чизе, ки барҷаста) дар тамоми массив аст.

Биёед аз раванди дарёфти унсури максималӣ аз массив гузарем

  • Максимум тағирёбандаро нигоҳ доред. Дар аввал арзиши онро ҳамчун унсури 0-ум аз массив дар он гузоред.
  • Нигоҳ доштани тағирёбанда барои нигоҳ доштани индекс. Дар ин ҷо, j.
  • Дар тамоми массив давра гузаронед
    • Ҳар дафъае, ки мо арзиши аз max бузургтарро дучор меоем
      • Тағирёбандаи max навсозӣ кунед
      • Арзиши нави индексро дар 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

Кодекси Java барои Пайдо кардани унсури қулла

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

Binarizing ҷустуҷӯ

Ҳоло, ки мо маънои хаттии худро тамом кардем, биёед ба расм бинарем модари ҳама чизҳои log (n) -ро.

Мо дар ин ҷо чӣ кор мекунем?

  • Ду нишондиҳандаро баланд ва паст нигоҳ доред
  • Нуқтаи миёнаро бо ёрии нишоннамоҳо ҳисоб кунед
    • Ҳар дафъа, унсури мобайн аз элементе, ки дар шафати он ҷойгир аст, бузургтар аст
      • Мо дар нимаи аввали массив ҷустуҷӯ кардани унсури калонтарро оғоз мекунем
      • Чаро?
        • Нимаи дуюм бешубҳа қуллаи худро ба нимаи аввал супурд, ки ба қоидаи мо бузургтар будан хиёнат мекунад
    • Ҳар дафъа, ки унсури мобайн аз унсури шафати он хурдтар аст
      • Мо дар ҷустуҷӯи унсуре, ки шояд аз ҳамсояҳо зиёдтар бошад, ба ҷустуҷӯ дар нимаи дуюми массив оғоз мекунем
      • Чаро?
        • Нимаи аввал бешубҳа қуллаи худро ба нимаи дуввум супурд, ки ба қоидаи мо бузургтар будан хиёнат кард
    • Онро такрор кунед, то он даме, ки пасттар аз баландтар баландтар шавад
    • Бозгаштан элемент дар ҳолати паст ҷойгир аст, зеро он аз иборат аст Унсури қуллаи 

Кодекси Java

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

Дар Мураккабии вақт аз равиши боло = O (log n)

Мураккабии фазо = О (1)

Адабиёт

Омӯзишро қатъ накунед ва яке аз усулҳои ҷолибтарини ҷобаҷогузории моро пайгирӣ кунед:

Воридшавӣ