Triplet Subsequence Artırılması LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Bloomberg Facebook google Über
ülgüc puluBaxılıb 15

Problem bəyanat :

Triplet Subsequence Artırılması LeetCode Həlli – Tam ədəd massivi verilmişdir nömrə, qayıt doğru üçlü indekslər varsa (i, j, k) belə i < j < k və ədədlər[i] < ədədlər[j] < ədədlər[k]. Əgər belə indekslər yoxdursa, qaytarın saxta.

Misal:

Misal 1:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Misal 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Məhdudiyyətlər:

Triplet Subsequence Artırılması LeetCode Həlli

 

Müşahidə:

  • Verilmiş məhdudiyyətlərdə massivin uzunluğu ola bilər 5*10^5, belə ki, kobud güc həlli O(n^2) və ya O(n^3) burada işləməyəcək, Brute force daha yaxşı bir şey etməliyik.
  • Biz i < j < k istəyirik və nums[i] < nums[j] < nums[k], əgər biz ədədlər[i] yaratmağa çalışsaq mümkün qədər kiçik həm də düzəldir  ədəd[j] kiçikdir lakin nums[j] ədədlərdən[i] böyük olmalıdır ona görə də bizə kömək edəcək.
  • Əgər müşahidə etsək, Xəsis alqoritm yaxşı işləyəcək.

Ən uzun artan alt ardıcıllığın variantı

  • 2 x və y dəyişənini saxlamalıyıq.
  • x indiyə qədər görülən ən kiçik ədəddir. x həm də indiyə qədər görülən bütün alt ardıcıllıqlar arasında ən kiçik sonuncu ədəddir.
  • 2 ölçülü bütün artan alt ardıcıllıqları götürsək və alt ardıcıllığı s[0], s[1] kimi təqdim etsək; onda y min(s[1]).
  • Hər hansı yeni z ədədi üçün z y-dən çox olarsa, bizim həllimiz var.

Alqoritm:

  • İki dəyişən başlayın Zamanorta ilə Tam ədəd.MAX_VALUE (Bütün MAKSİMUM DƏYƏR). 

int left=Tam.MAX_VALUE;

int orta = Tam ədəd.MAX_VALUE;

  • Dan təkrarlayın soldan sağa ci nömrə serial.

  • İterasiya zamanı aşağıdakı elementi tapmağa çalışın sağ > orta > sol şərt və bu elementi adlandırın sağ.

int sağ = ədədlər[i];

 

  • Triplet Subsequence Artırılması LeetCode HəlliPin

 

 

  • Əgər sağ kiçikdirr-dən solt dəyişəni sonra düzəldin sol = sağ.

Triplet Subsequence Artırılması LeetCode HəlliPin

 

                 

  • Əgər hüququ var arasında bu solt və orta sonra ortadan doğru yerə keçin orta = sağ. Triplet Subsequence Artırılması LeetCode HəlliPin
  • Əgər düzdür daha böyükdür solt və orta sonra qayıdın doğru.
  • Döngə bitdikdən sonra Artan almadıqsa Triplet Sonrakı sonra qayıdın saxta.

Kod:

Üçlü Ardıcıllığı Artırmaq üçün Java Kodu:

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n= nums.length;
        int left=Integer.MAX_VALUE;
        int middle=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int right=nums[i];
            if(right<left){
                left=right;
            }
            else if(right<middle && right > left){
                middle = right;
            }
            else if(right>middle&& right>left)return true;
        }
        return false;
    }
    
}

Üçlü Ardıcıllığı Artırmaq üçün C++ Kodu:

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
         int n= nums.size();
        int left=INT_MAX;
        int middle=INT_MAX;
        for(int i=0;i<n;i++){
            int right=nums[i];
            if(right<left){
                left=right;
            }
            else if(right<middle && right > left){
                middle = right;
            }
            else if(right>middle&& right>left)return true;
        }
        return false; 
    }
};

Üçlü Ardıcıllığın Artırılması üçün Mürəkkəblik Təhlili LeetCode Həlli:

Zamanın mürəkkəbliyi:

O (N)

Kosmik Mürəkkəblik:

O(1) çünki biz heç bir əlavə yerdən istifadə etmirik.

Translate »