n Leetcode Həllinin k-ci Faktoru

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Cisco Expedia cuqquldamaq
RiyaziyyatBaxılıb 48

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

n Leetcode Həllinin k-ci Faktoru: sizə iki müsbət tam ədəd verildiyini bildirir n və k. A amil tam ədəd n tam ədəd kimi müəyyən edilir i hara n % i == 0.

Bütün amillərin siyahısını nəzərdən keçirin n sıralanır artan sifariş, qayıt bu kth amil bu siyahıda və ya qaytarın -1 if n -dən azdır k amillər.

Misal 1:

Input:

n = 12, k = 3

Çıxış:

3

Explanation:

Faktorlar siyahısı [1, 2, 3, 4, 6, 12], 3-cü amil 3-dür.

Misal 2:

Input:

n = 7, k = 2

Çıxış:

7

Explanation:

Faktor siyahısı [1, 7] və 2-dirnd əmsalı 7-dir.

Misal 3:

Input:

n = 4, k = 4

Çıxış:

-1

Explanation:

Faktorların siyahısı [1, 2, 4] və yalnız 3 amil var. -1 qayıtmalıyıq.

Yanaşma

Idea:

Tutaq ki, bizə n ədədi verilib, biz 1-dən n-ə qədər bir dövrə keçirəcəyik.

Hər bir iterasiya üçün n%i==0, yəni n-in i-yə bölünüb-bölünmədiyini yoxlayacağıq. Eyni zamanda, say dəyişənini də artıracağıq.

Əgər müəyyən i üçün say k-yə bərabərdirsə, onda biz n-nin k-ci faktorunu tapmışıq və biz i-ni qaytaracağıq.

Əgər n-nin belə k-ci faktoru tapılmazsa, onda -1 qaytarın. Ən pis halda dövrə n-ə qədər işləyir, ona görə də O(n) ən pis zaman mürəkkəbliyidir.

Kodu

n Leetcode C++ Həllinin k-ci Faktoru:

class Solution {
public:
    int kthFactor(int n, int k) {
       int count=0;
       for(int i=1;i<=n;i++)
       {
           if(n%i==0)count++;
           if(count==k)return i;
       }
       return -1;
   }
};

n Leetcode Java Həllinin k-ci Faktoru:

class Solution {
    public int kthFactor(int n, int k) {
        int count = 0;
        for(int i=1;i<=n;i++){
            if(n%i==0){
                count++;
            }
            if(count==k){
                return i;
            }
        }
        return -1;
    }
}

n Leetcode Python Həllinin k-ci Faktoru:

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
       count = 0
       for i in range(1, n + 1):
           if math.fmod(n, i)==0:
               count += 1
           if count == k:
               return i
       return -1

n LeetCode Həllinin k-ci Faktoru üçün Mürəkkəblik Təhlili:

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n). 1-dən n-ə qədər amilləri tapmağa başlayırıq və ən pis halda, n-ə qədər təkrarlanır. Beləliklə, ən pis zaman mürəkkəbliyi O(n)-dir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz burada heç bir əlavə yerdən istifadə etmirik.

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