Üçüncü Maksimum Sayı Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Facebook googleBaxılıb 70

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Üçüncü Maksimum Say Leetcode Həlli – Tam ədədlər massivi verilmişdir nums, qayıt bu üçüncü fərqli maksimum bu massivdəki nömrə. Üçüncü maksimum yoxdursa, onu qaytarın maksimum nömrə.

misal

Input:

 nums = [3,2,1]

Çıxış:

 1

Explanation:

The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Input:

 nums = [2,2,3,1]

Çıxış:

 1

Explanation:

The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

Yanaşma

Bu, 3 dəyəri izləyən və daha çox sayda göründükdə bütün lazımi dəyərləri yeniləyən sadə bir həlldir. Birinci halda, dəyər maxValue1-dən böyükdürsə, əvvəlcə digər dəyərlər yenilənməlidir (əsasları aşağı itələmək).

Bundan əlavə, yeni dəyərin təkrar (ən yüksək) dəyərlərə səbəb olan daha böyük dəyərlərdən biri ilə eyni olmamasını təmin etməliyik.

Nəhayət, elementlərin sayının 3-dən az olub olmadığını yoxlamaq üçün yoxlamam var. Əgər belədirsə, ən yüksək dəyəri qaytarın. Əks halda, 3-cü maksimum rəqəmi qaytarın.

Idea:

Əsas ideya massivdən maksimum üç elementi saxlamaq üçün 3 dəyişəni saxlamaqdır, tutaq ki, mx1, mx2 və mx3 üç dəyişəndir. mx1 ilk maksimumu bildirir, mx2 ikincini bildirir maksimum,mx3 üçüncü maksimumu bildirir.

İndi massivdən keçirik,

  1. bir nömrə tapsaq mx1-dən böyük, sonra biz mx1-i yeniləyəcəyik, lakin burada tutma ondan ibarətdir ki, mx1 dəyəri burada dəyişir, ona görə də biz mx1-in əvvəlki dəyərini mx2-yə saxlamalıyıq, indi mx2 də buradan dəyişəcək, ona görə də mx2-nin əvvəlki dəyərini mx3-ə saxlayaq.
  2. Bir nömrə tapsaq mx2-dən böyük, və mx1-ə bərabər deyilsə, onda biz mx2-ni yeniləməliyik, lakin burada da mx2-nin əvvəlki dəyərini mx3-ə saxlamalıyıq.
  3. tapsaq a mx3-dən böyük rəqəm,  və mx1 və mx2-yə bərabər deyil, biz mx3-ü yeniləyirik.

Kodu

Üçüncü Maksimum Say üçün C++ Kodu

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        int n = nums.size();
        
        long long int mx1 = -1e15;
        long long int mx2 = -1e15;
        long long int mx3 = -1e15;
        
        for(int i=0;i<n;i++){
            if(nums[i] > mx1){
                mx3 = mx2;
                mx2 = mx1;
                mx1 = nums[i];
            }
            else if(nums[i] > mx2 && nums[i]!=mx1){
                mx3 = mx2;
                mx2 = nums[i];
            }
            else if(nums[i] > mx3 && nums[i]!=mx1 && nums[i]!=mx2){
                mx3 = nums[i];
            }
        }
        
        return mx3==-1e15 ? mx1 : mx3;   
    }
};

Üçüncü Maksimum Nömrə üçün Java Kodu

class Solution{
    public int thirdMax(int[] nums) {
        Integer max1 = null;
        Integer max2 = null;
        Integer max3 = null;
        for (Integer n : nums) {
            if (n.equals(max1) || n.equals(max2) || n.equals(max3)) continue;
            if (max1 == null || n > max1) {
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (max2 == null || n > max2) {
                max3 = max2;
                max2 = n;
            } else if (max3 == null || n > max3) {
                max3 = n;
            }
        }
        return max3 == null ? max1 : max3;
    }
}

Üçüncü Maksimum Say Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Bütün massivi yalnız bir dəfə keçdiyimiz üçün zaman mürəkkəbliyi O(n)-dir.

Kosmik Mürəkkəblik

Biz yalnız üç dəyişən8 istifadə edirik, buna görə də kosmik mürəkkəblik O(1) olur.

Crack Sistemi Dizayn Müsahibələri
Translate »