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

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

이 게시물은 임계 값 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 »