Çirkin Nömrə II LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Citadel Facebook google microsoftBaxılıb 22

Problem bəyanat

Ugly Number II LeetCode Solution – An çirkin nömrə əsas amilləri məhdud olan müsbət tam ədəddir 23və 5.

Bir tam verilir n, qayıt bu nth çirkin nömrə.

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Izahat

Bizdə massiv var k ilk n çirkin nömrədən. Biz yalnız başlanğıcda birincisini bilirik, o da 1. Sonra

k[1] = min( k[0]x2, k[0]x3, k[0]x5). Cavab k[0]x2-dir. Beləliklə, biz 2-nin göstəricisini 1-ə keçirik. Sonra test edirik:

k[2] = min( k[1]x2, k[0]x3, k[0]x5). Və s. 6 və 2-ün hər iki göstəricisini yönləndirməmiz lazım olan 3 kimi hallarda diqqətli olun.

x burada vurmadır.

Yanaşma

Gəlin bu problemi ümumi vəziyyət üçün həll edək: bu, təkcə üçün deyil 2,3,5 bölənlər, lakin onlardan hər hansı biri və istənilən sayda üçün. factors = [2,3,5] və k=3 bizim vəziyyətimizdə.
Qoy Numbers bir sıra olmaq, biz bütün saxlamaq çirkin nömrələri. Həm də qeyd edin ki, hər hansı bir çirkin rəqəm başqa bir çirkin rəqəmdir, vurulur 23 or 5. Beləliklə, qoy starts ilə vurulduqda çirkin ədədlərin göstəriciləri olsun 23 or 5 müvafiq olaraq, cari ümumi maksimum çirkin nömrədən böyük olan ən kiçik çirkin ədədi yaradır. Bunu daha yaxşı başa düşmək üçün bir neçə ilk addım ataq:

  1. starts = [0,0,0] nömrələr üçün 2,3,5, Belə ki, new_num = min(1*2,1*3,1*5) = 2, və indi starts = [1,0,0]Numbers = [1,2].
  2. starts = [1,0,0], Belə ki, new_num = min(2*2,1*3,1*5) = 3, və indi starts = [1,1,0]Numbers = [1,2,3].
  3. starts = [1,1,0], Belə ki, new_num = min(2*2,2*3,1*5) = 4, indi isə starts = [2,1,0]Numbers = [1,2,3,4].
  4. starts = [2,1,0], Belə ki, new_num = min(3*2,2*3,1*5) = 5, indi isə starts = [2,1,1]Numbers = [1,2,3,4,5].
  5. starts = [2,1,1], Belə ki, new_num = min(3*2,2*3,2*5) = 6, buna görə də bu vəziyyətdə diqqətli olaq: ​​bizdən iki ədəd artırmalıyıq start, çünki yeni nömrəmiz 6 hər ikisinə bölmək olar 2 və 3, indi isə starts = [3,2,1]Numbers = [1,2,3,4,5,6].
  6. starts = [3,2,1], Belə ki, new_num = min(4*2,3*3,2*5) = 8, indi isə starts = [4,2,1]Numbers = [1,2,3,4,5,6,8]
  7. starts = [4,2,1], Belə ki, new_num = min(5*2,3*3,2*5) = 9, indi isə starts = [4,3,1]Numbers = [1,2,3,4,5,6,8,9].
  8. starts = [4,3,1], Belə ki, new_num = min(5*2,4*3,2*5) = 10, ona görə də bizdən iki elementi yeniləmək lazımdır starts və indi starts = [5,3,2]Numbers = [1,2,3,4,5,6,8,9,10]
  9. starts = [5,3,2], Belə ki, new_num = min(6*2,4*3,3*5) = 12, biz yenidən iki elementi yeniləməliyik starts, və indi starts = [6,4,2]Numbers = [1,2,3,4,5,6,8,9,10,12].
  10. starts = [6,4,2], Belə ki, new_num = min(8*2,5*3,3*5) = 15, biz yenidən iki elementi yeniləməliyik starts, və indi starts = [6,5,3]Numbers = [1,2,3,4,5,6,8,9,10,12,15].

Kodu

Çirkin Nömrə II üçün C++ Kodu

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n <= 0) return false; // get rid of corner cases 
        if(n == 1) return true; // base case
        int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5
        vector<int> k(n);
        k[0] = 1;
        for(int i  = 1; i < n ; i ++)
        {
            k[i] = min(k[t2]*2,min(k[t3]*3,k[t5]*5));
            if(k[i] == k[t2]*2) t2++; 
            if(k[i] == k[t3]*3) t3++;
            if(k[i] == k[t5]*5) t5++;
        }
        return k[n-1];
    }
};

Çirkin Nömrə II üçün Java Kodu

public class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for(int i=1;i<n;i++){
            int min = Math.min(Math.min(factor2,factor3),factor5);
            ugly[i] = min;
            if(factor2 == min)
                factor2 = 2*ugly[++index2];
            if(factor3 == min)
                factor3 = 3*ugly[++index3];
            if(factor5 == min)
                factor5 = 5*ugly[++index5];
        }
        return ugly[n-1];
    }
}

Çirkin Nömrə II üçün Python Kodu

class Solution:
    def nthUglyNumber(self, n):
        factors, k = [2,3,5], 3
        starts, Numbers = [0] * k, [1]
        for i in range(n-1):
            candidates = [factors[i]*Numbers[starts[i]] for i in range(k)]
            new_num = min(candidates)
            Numbers.append(new_num)
            starts = [starts[i] + (candidates[i] == new_num) for i in range(k)]
        return Numbers[-1]

Ugly Number II LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (N)

Kosmik Mürəkkəblik

O (N)

Referans: https://en.wikipedia.org/wiki/Factor

Şərh yaz

Translate »