임계 값 Leetcode 솔루션에서 최소 제수 찾기

난이도 중급
자주 묻는 질문 AppDynamics 구글 SAP 월마트 연구소
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 77

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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 배열의 최대 값으로자를 수 있습니다.

임계 값 Leetcode 솔루션에서 가장 작은 제수 찾기

  • 이제 우리는 최소 및 최대 우리 손에있는 제수 값. 이제 우리의 유일한 임무는 가장 작은 제수를 찾는 것입니다.
  • [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) 답을 저장하기 위해서만 메모리를 사용하기 때문입니다.

참조

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