しきい値リートコードソリューションが与えられた最小の除数を見つける


難易度 ミディアム
よく聞かれる AppDynamics Google SAP ウォルマート・ラボ
リートコード

この投稿は、しきい値リートコードソリューションが与えられた場合の最小除数の検索に関するものです。

問題文

問題「しきい値が与えられた最小の除数を見つける」では、nums配列としきい値が与えられます。 変数「結果」は、配列内の要素が除数で除算されたときのすべての回答の合計として定義されます。 私たちのタスクは、結果がしきい値以下になるように、除数の可能な最小値を見つけることです。

配列内の要素を除数で除算する場合、除算の答えとして上限値を考慮します。 除数は positive integer .

arr=[1,2,5,9], threshold=6
5

説明: すべての要素を1で割ると、結果は(1 + 2 + 5 + 9)17になり、6より大きくなります。したがって、除数の値を増やして結果の値を減らします。

ここで、除数= 4を考慮すると、結果は(1 + 1 + 2 + 3)7であり、6より大きくなります。したがって、除数の値を増やして結果の値を減らします。

divisor = 5を考えると、結果は(1 + 1 + 1 + 2)6になります。したがって、答えは5です。

アプローチ

私たちの仕事は見つけることです 最小値 除数の。 それで、最初に何ができるかについて考えましょう 最小と最大 除数の値。

  • 除数は正の整数であるため、除数の最小値は1です。
  • 除数の最大値について言えば、これより大きい値でも常に同じ答えが得られるため、nums配列の最大値にトリミングできます。

しきい値リートコードソリューションが与えられた場合の最小除数を見つける

  • 今、私たちは持っています 最小値と最大値 私たちの手にある除数の値。 今、私たちの唯一のタスクは、最小の除数を見つけることです。
  • [min、max]の範囲の各値を手動で確認できますが、範囲の値が並べ替えられるため、 二分探索アルゴリズム より良い時間計算量のために。
  • start <= endのときにループが終了するように、除数の最小値を見つけようとしています。 最終的に、開始には最終的な回答が含まれるため、その値を返します。

コード

しきい値リートコードソリューションを指定して最小の除数を見つけるための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

しきい値リートコードソリューションが与えられた場合の最小除数の検索の複雑さの分析

時間の複雑さ

上記のコードの時間計算量は O(N) nums配列をXNUMX回だけトラバースしているためです。 ここで、nはnums配列の長さです。

スペースの複雑さ

O(1) 答えを保存するためだけにメモリを使用しているからです。

リファレンス