Rotated Sorted Array II LeetCode Həllində Minimumu tapın

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Facebook google microsoft Kahin ÜberBaxılıb 20

Problem bəyanat

Rotated Sorted Array II LeetCode Həllində Minimumu tapın – Tutaq ki, uzunluq massivi n artan qaydada sıralanır döndü arasında 1 və n dəfə. Məsələn, massiv nums = [0,1,4,4,5,6,7] ola bilər:

  • [4,5,6,7,0,1,4] fırlansaydı 4 dəfə.
  • [0,1,4,4,5,6,7] fırlansaydı 7 dəfə.

Diqqət edin fırlanan bir sıra [a[0], a[1], a[2], ..., a[n-1]] Massivdə 1 dəfə nəticə verir [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Çeşidlənmiş fırlanan massiv nəzərə alınmaqla nums ehtiva edə bilər dublikatlar, qayıt bu massivin minimum elementi.

Ümumi əməliyyat addımlarını mümkün qədər azaltmalısınız.

Misal:

giriş: [1,2,3]

çıxış - 1

İzahat:

nums massivindəki minimum element 1-dir.

giriş: [2,2,2,0,1]

çıxış - 0

İzahat:

nums massivindəki minimum element 0-dır. Beləliklə, biz 0 qaytarırıq.

Yanaşma:

Fikir

Massiv çeşidləndiyi üçün a tətbiqini düşünmək olar ikili axtarış burada, lakin sadə ikili axtarış burada işləməyəcək, çünki massiv də fırlanır, ona görə də nümunədən istifadə edərək problemi diqqətlə təhlil etməli olacağıq.

Alqoritm-

  1. Saxlamaq iki göstərici axtarış məkanımızın ən aşağı və ən yüksək sərhədlərini göstərən aşağı və yüksək.
  2. Sonra göstəricilərdən hər hansı birini müxtəlif vəziyyətlərə uyğun hərəkət etdirərək axtarış sahəsini azaldırıq.
  3. Əgər orta dəyər yüksək dəyərdən azdırsa, bu o deməkdir ki, orta və yüksək arasında olan elementlər azalmayan ardıcıllıqla sıralanır. minimum dəyər solda olacaq, biz belə edirik, yüksək = orta.
  4. Əgər orta dəyər yüksək dəyərdən böyükdürsə, bu o deməkdir ki, aşağı və orta arasında olan elementlər azalmayan ardıcıllıqla sıralanır. minimum dəyər sağda olacaq biz də edirik aşağı = orta+1.
  5. Orta dəyər yüksək dəyərə bərabərdirsə, yüksək dəyəri 1 azaldın,  yüksək = yüksək-1;
  6. Yuxarıdakı təlimatları aşağı yüksəkə bərabər olana qədər yerinə yetirin.

Səmərəsizdir

Rotated Sorted Array II LeetCode Həllində Minimumu tapınPin

Səmərəli

Rotated Sorted Array II LeetCode Həllində Minimumu tapınPin

Məsələn -

ədədlər – [2,2,2,3,4,5,5,5,0,0,1,1,1,1,2,2,2]

Addım 1

aşağı = 0 , yüksək = 16

orta = (aşağı+yüksək)/2 = 8

indi nums[mid] < nums[high] olduğundan, bu o deməkdir ki, biz sola hərəkət etməliyik,

yüksək = orta;

addım - 2

aşağı = 0, yüksək = 8;

orta = (aşağı+yüksək)/2 = 4;

nums[mid] > nums[high] , sağa hərəkət edin,

aşağı = orta+1;

addım - 3

aşağı = 5 , yüksək = 8;

orta = (5+8)/2 = 6;

nums[mid] > nums[high] , sağa hərəkət edin,

aşağı = orta+1;

addım - 4

aşağı = 7 , yüksək = 8;

orta = (7+8)/2 = 7;

nums[mid] > nums[high] , sağa hərəkət edin,

aşağı = orta+1;

aşağı == yüksək == 8, bu bizim minimum element indeksimizdir,

minimum element = ədədlər[8] = 0;

Kod -

C ++ kodu

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        
        int str=0,end=n-1;
        
        while(str < end){
            int mid = str + (end-str)/2;
            
            if(nums[mid] < nums[end]){
                end = mid;
            }
            else if(nums[mid] > nums[end]){
                str = mid+1;
            }
            else{
                end-=1;
            }
        }
        return nums[str];
    }
};

Java kodu

class Solution {
    public int findMin(int[] nums) { 
        int low = 0;
        int high = nums.length - 1; 
        while(low < high){ 
            int mid = (low+high)/2; 
            if(nums[mid] < nums[high]){
                high = mid; 
            } 
            else if(nums[mid] > nums[high]){
                low = mid+1; 
            } 
            else{
                high -= 1; 
            } 
        } 
        return nums[low]; 
    }
}

Rotated Sorted Array II-də Minimum Tapmaq üçün Zaman və Məkan Mürəkkəblik Təhlili LeetCode Həll

Zamanın mürəkkəbliyi -

a istifadə etdiyimiz üçün ikili axtarış alqoritmi və axtarış sahəsini yarıya endirərək, orta zaman mürəkkəbliyidir O (logn), lakin Ən pis halda bütün elementlər bərabərdirsə, o zaman mürəkkəblikdir O (n).

Kosmik mürəkkəblik -

Biz burada əlavə yer istifadə etmirik, Kosmosun mürəkkəbliyi O(1).

Translate »