n Leetcode 솔루션의 k번째 인수

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 시스코 Expedia Twitter
수학조회수 48

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

n Leetcode 솔루션의 k번째 인수: 두 개의 양의 정수가 주어졌음을 나타냅니다. n 및 k. 에이 인자 정수의 n 정수로 정의 i 어디에 n % i == 0.

의 모든 요인 목록을 고려하십시오. n 정렬 오름차순, 반환 전에, kth 인자 이 목록에서 또는 반환 -1 if n 보다 적은 k 요인.

예 1 :

입력:

n = 12, k = 3

출력:

3

설명 :

요인 목록은 [1, 2, 3, 4, 6, 12]이고 세 번째 요인은 3입니다.

예 2 :

입력:

n = 7, k = 2

출력:

7

설명 :

요인 목록은 [1, 7]이고 2는nd 계수는 7입니다.

예 3 :

입력:

n = 4, k = 4

출력:

-1

설명 :

요인 목록은 [1, 2, 4]이며 요인은 3개뿐입니다. -1을 반환해야 합니다.

접근

아이디어 :

숫자 n이 주어지면 1에서 n까지 루프를 실행합니다.

각 반복에 대해 n%i==0 즉 n이 i로 나눌 수 있는지 확인합니다. 동시에 count 변수를 증가시킵니다.

만약 count가 특정 i에 대해 k와 같다면, 우리는 n의 k번째 인자를 찾았고, i를 반환할 것입니다.

n의 k번째 인자가 발견되지 않으면 -1을 반환합니다. 최악의 경우 루프는 n까지 실행되므로 O(n)은 최악의 시간 복잡도입니다.

암호

n Leetcode C++ 솔루션의 k번째 요소:

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 솔루션의 k번째 요소:

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 솔루션의 k번째 요소:

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 솔루션의 k번째 요소에 대한 복잡성 분석:

시간 복잡성

위 코드의 시간 복잡성은 의 위에). 우리는 1에서 n까지 요소를 찾기 시작하고 최악의 경우 n까지 반복합니다. 따라서 최악의 시간 복잡도는 O(n)입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 여기에서 추가 공간을 사용하지 않기 때문입니다.

균열 시스템 설계 인터뷰
Translate »