시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
이 게시물은 임계 값 Leetcode 솔루션에서 가장 작은 제수 찾기에 있습니다.
차례
문제 설명
”임계 값이 주어진 최소 제수 찾기”문제에서 nums 배열과 임계 값이 제공됩니다. 변수 "결과"는 배열의 요소를 제수로 나눌 때 모든 답변의 합으로 정의됩니다. 우리의 임무는 결과가 임계 값보다 작거나 같은 방식으로 제수의 가능한 가장 작은 값을 찾는 것입니다.
배열의 요소를 제수로 나눌 때 천장 값을 나눗셈에 대한 답으로 간주합니다. 제수는 양의 정수.
예
arr=[1,2,5,9], threshold=6
5
설명 : 모든 요소를 1로 나눌 때 결과는 (1 + 2 + 5 + 9) 17이됩니다. 이는 6보다 큽니다. 따라서 결과 값을 줄이기 위해 제수 값을 늘릴 것입니다.
이제 divisor = 4를 고려하면 결과는 1보다 큰 (1 + 2 + 3 + 7) 6이됩니다. 따라서 결과 값을 줄이기 위해 제수 값을 늘릴 것입니다.
divisor = 5를 고려하면 결과는 (1 + 1 + 1 + 2) 6입니다. 따라서 답은 5입니다.
접근
우리의 임무는 최소값 제수의. 그래서 먼저 무엇이 될 수 있는지 생각해 봅시다. 최소 및 최대 제수의 값.
- 제수가 양의 정수이기 때문에 제수의 최소값은 1입니다.
- 제수의 최대 값에 대해 이야기하면 이보다 큰 값도 항상 동일한 답을 제공하기 때문에 nums 배열의 최대 값으로자를 수 있습니다.
- 이제 우리는 최소 및 최대 우리 손에있는 제수 값. 이제 우리의 유일한 임무는 가장 작은 제수를 찾는 것입니다.
- [min, max] 범위의 각 값을 수동으로 확인할 수 있지만 범위의 값이 정렬되어 있으므로 이진 검색 알고리즘 더 나은 시간 복잡성을 위해.
- 우리는 start <= end 일 때 루프가 끝나도록 제수의 가장 작은 값을 찾으려고합니다. 결국 시작에는 최종 답변이 포함되므로 그 값을 반환합니다.
암호
임계 값 Leetcode 솔루션에서 최소 제수 찾기를위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int smallestDivisor(vector<int>& nums, int threshold) {
int s=1,e=*max_element(nums.begin(),nums.end());
int n=nums.size();
while(s<=e)
{
int mid=s+(e-s)/2;
int sum=0;
for(int i=0;i<n;i++)
sum=sum+(nums[i]+mid-1)/mid;
if(sum<=threshold)
{
e=mid-1;
}
else
{
s=mid+1;
}
}
return s;
}
int main()
{
vector<int> arr = {1,2,5,9};
int threshold = 6;
cout<<smallestDivisor(arr,threshold)<<endl;
return 0;
}
5
임계 값 Leetcode 솔루션에서 최소 제수 찾기를위한 Java 코드
import java.util.Arrays;
public class Tutorialcup {
public static int smallestDivisor(int[] nums, int threshold) {
int s=1,e=Arrays.stream(nums).max().getAsInt();
int n=nums.length;
while(s<=e)
{
int mid=s+(e-s)/2;
int sum=0;
for(int i=0;i<n;i++)
sum=sum+(nums[i]+mid-1)/mid;
if(sum<=threshold)
{
e=mid-1;
}
else
{
s=mid+1;
}
}
return s;
}
public static void main(String[] args) {
int [] arr = {1,2,5,9};
int threshold = 6;
int ans= smallestDivisor(arr,threshold);
System.out.println(ans);
}
}
5
임계 값 Leetcode 솔루션에서 최소 제수 찾기의 복잡성 분석
시간 복잡성
위 코드의 시간 복잡성은 O (N) nums 배열을 한 번만 순회하기 때문입니다. 여기서 n은 nums 배열의 길이입니다.
공간 복잡성
O (1) 답을 저장하기 위해서만 메모리를 사용하기 때문입니다.
