Çirkin Nömrə II LeetCode Həlli

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

Problem bəyanat

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

Bir tam verilir n, qayıt bu n^th ç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 2, 3 or 5. Beləliklə, qoy starts ilə vurulduqda çirkin ədədlərin göstəriciləri olsun 2, 3 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:

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].
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].
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].
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].
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].
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]
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].
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]
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].
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