ស្វែងរកអ្នកបែងចែកតូចជាងគេបំផុតដែលផ្តល់ជូននូវដំណោះស្រាយឡេតូហ្សិនឡេតកូដ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ AppDynamics ក្រុមហ៊ុន google SAP បន្ទប់ពិសោធន៍វ៉លម៉ាត
LeetCode

ប្រកាសនេះគឺមាននៅលើសែរកតូចតាចតូចជាងគេបំផុតដែលផ្តល់ជូននូវដំណោះស្រាយឡេតថិនឡេសសឺរ

សេចក្តីថ្លែងការណ៍បញ្ហា

នៅក្នុងបញ្ហា "រកអ្នកបែងចែកតូចជាងគេដែលផ្តល់កម្រិត" យើងត្រូវបានគេផ្តល់លេខជួរនិងតម្លៃកំណត់។ អថេរលទ្ធផលត្រូវបានកំណត់ជាផលបូកនៃចម្លើយទាំងអស់នៅពេលធាតុនៅក្នុងអារេត្រូវបានបែងចែកដោយអ្នកចែក។ ភារកិច្ចរបស់យើងគឺស្វែងរកតម្លៃតូចបំផុតដែលអាចធ្វើទៅបាននៃវិធីចែកតាមរបៀបដែលលទ្ធផលគឺតូចជាងឬស្មើនឹងកំរិត។

នៅពេលយើងបែងចែកធាតុនៅក្នុងអារេដោយអ្នកបែងចែកយើងកំពុងពិចារណាលើតម្លៃពិដានជាចម្លើយនៃការបែងចែក។ អ្នកបែងចែកគួរតែជាក ចំនួនគត់វិជ្ជមាន.

ឧទាហរណ៍

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

ការពន្យល់: នៅពេលយើងបែងចែកធាតុទាំងអស់ដោយលទ្ធផល ១ គឺ (១ + ២ + ៥ + ៩) ១៧ ដែលធំជាង ៦ ។ ដូច្នេះយើងនឹងបង្កើនតម្លៃតួចែកដើម្បីកាត់បន្ថយតម្លៃលទ្ធផល។

ឥឡូវប្រសិនបើយើងពិចារណាលេខចែក = ៤ នោះលទ្ធផលគឺ (១ + ១ + ២ + ៣) ៧ ដែលធំជាង ៦ ។ ដូច្នេះយើងនឹងបង្កើនតម្លៃតួចែកដើម្បីកាត់បន្ថយតម្លៃលទ្ធផល។

ប្រសិនបើយើងពិចារណាលេខចែក = ៥ ពេលនោះលទ្ធផលគឺ (១ + ១ + ១ + ២) ៦ ។ ដូច្នេះចម្លើយគឺ ៥ ។

វិធីសាស្រ្ត

ភារកិច្ចរបស់យើងគឺស្វែងរកឯកសារ តម្លៃអប្បបរមា របស់អ្នកចែក។ ដូច្នេះដំបូងយើងគិតអំពីអ្វីដែលអាចជា អប្បបរមានិងអតិបរមា តម្លៃនៃតួចែក។

  • តម្លៃអប្បបរមានៃតួចែកគឺ ១ ពីព្រោះលេខចែកគឺជាចំនួនគត់វិជ្ជមាន។
  • និយាយអំពីតម្លៃអតិបរិមានៃតួចែកយើងអាចកាត់វាទៅជាតម្លៃអតិបរិមាក្នុងជួរលេខពីព្រោះតម្លៃធំជាងនេះនឹងផ្តល់ចម្លើយដដែល។

ស្វែងរកអ្នកចែកតូចជាងគេដែលផ្តល់នូវដំណោះស្រាយឡេតូលេខកូដ

  • ឥឡូវយើងមាន អប្បបរមានិងអតិបរមា តម្លៃនៃតួចែកនៅក្នុងដៃរបស់យើង។ ឥឡូវនេះភារកិច្ចតែមួយគត់របស់យើងគឺស្វែងរកអ្នកបែងចែកតូចបំផុត។
  • យើងអាចត្រួតពិនិត្យតម្លៃនីមួយៗនៅក្នុងជួរ [នាទីអតិបរិមា] ប៉ុន្តែដោយសារតម្លៃនៅក្នុងជួរត្រូវបានតម្រៀបដូច្នេះយើងនឹងប្រើ ក្បួនដោះស្រាយការស្វែងរកគោលពីរ សម្រាប់ភាពស្មុគស្មាញពេលវេលាល្អប្រសើរ។
  • យើងកំពុងព្យាយាមរកតម្លៃតូចបំផុតនៃតួចែកដូច្នេះរង្វិលជុំនឹងចប់នៅពេលចាប់ផ្តើម <= ចប់។ នៅចុងបញ្ចប់ការចាប់ផ្តើមនឹងមានចម្លើយចុងក្រោយដូច្នេះយើងនឹងប្រគល់តម្លៃរបស់វាមកវិញ។

លេខកូដ

លេខកូដ 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

កូដចាវ៉ាសម្រាប់ស្វែងរកអ្នកបែងចែកតូចជាងគេបំផុតដែលបានផ្តល់នូវដំណោះស្រាយឡេតកូដលេខកូដ

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

ការវិភាគភាពស្មុគស្មាញនៃការស្វែងរកអ្នកចែកតូចជាងគេដែលផ្តល់នូវដំណោះស្រាយឡេតូលេខកូដ

ភាពស្មុគស្មាញពេលវេលា

ពេលវេលាស្មុគស្មាញនៃលេខកូដខាងលើគឺ អូរ (n) ពីព្រោះយើងកំពុងត្រួសត្រាយជួរនៃចំនួនតែមួយដងប៉ុណ្ណោះ។ នៅទីនេះ n គឺជាប្រវែងនៃអារេលេខ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ពីព្រោះយើងប្រើអង្គចងចាំដើម្បីទុកចម្លើយតែប៉ុណ្ណោះ។

ឯកសារយោង