시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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) 여기에서 추가 공간을 사용하지 않기 때문입니다.
