ຊອກຫາພະແນກຂະ ໜາດ ນ້ອຍທີ່ສຸດທີ່ໄດ້ຮັບດ້ວຍ Threshold Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ AppDynamics ກູໂກ SAP Walmart Labs
LeetCode

ໂພສນີ້ແມ່ນກ່ຽວກັບ Find Divisor ຂະ ໜາດ ນ້ອຍທີ່ສຸດໂດຍການໃຫ້ Threshold Leetcode Solution

ບັນຫາບັນຫາ

ໃນບັນຫາ” ຊອກຫາການແບ່ງປັນຂະ ໜາດ ນ້ອຍທີ່ສຸດໃຫ້ເປັນລະດັບ” ພວກເຮົາໄດ້ຖືກຈັດໃຫ້ມີຕົວເລກເປັນ ຈຳ ນວນຫລາຍແລະມີຄ່າ ສຳ ຮອງ. "ຜົນໄດ້ຮັບ" ທີ່ມີຕົວປ່ຽນແປງໄດ້ຖືກ ກຳ ນົດເປັນຜົນລວມຂອງ ຄຳ ຕອບທັງ ໝົດ ເມື່ອອົງປະກອບຕ່າງໆໃນອາເລຖືກແບ່ງອອກໂດຍເຄື່ອງ ຈຳ ແນກ. ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາມູນຄ່ານ້ອຍທີ່ສຸດທີ່ເປັນໄປໄດ້ຂອງການແບ່ງປັນດ້ວຍວິທີດັ່ງກ່າວເຊິ່ງຜົນໄດ້ຮັບຈະນ້ອຍກ່ວາຫຼືເທົ່າກັບລະດັບທີ່ຕັ້ງໄວ້.

ເມື່ອພວກເຮົາແບ່ງປັນສ່ວນປະກອບໃນອາເລໂດຍພະນັກງານແບ່ງປັນ, ພວກເຮົາ ກຳ ລັງພິຈາລະນາມູນຄ່າເພດານເປັນ ຄຳ ຕອບ ສຳ ລັບການແບ່ງ. ພະແນກຄວນຈະເປັນ ເລກເຕັມໃນທາງບວກ.

ຍົກຕົວຢ່າງ

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 ເພາະວ່າຕົວເລກແມ່ນຕົວເລກບວກ.
  • ເວົ້າເຖິງມູນຄ່າສູງສຸດຂອງຕົວເລກພວກເຮົາສາມາດຕັດມັນໃຫ້ມີຄ່າສູງສຸດໃນແຖວຕົວເລກເພາະວ່າຄ່າທີ່ສູງກວ່ານີ້ຍັງຈະຕອບໃຫ້ຄືກັນ.

ຊອກຫາພະແນກຂະ ໜາດ ນ້ອຍທີ່ສຸດດ້ວຍວິທີແກ້ໄຂບັນຫາ Leetcode

  • ດຽວນີ້ພວກເຮົາມີ ຕໍາ່ສຸດທີ່ແລະສູງສຸດ ມູນຄ່າຂອງການແບ່ງປັນຢູ່ໃນມືຂອງພວກເຮົາ. ດຽວນີ້ວຽກງານດຽວຂອງພວກເຮົາແມ່ນຊອກຫາຜູ້ແບ່ງປັນຂະ ໜາດ ນ້ອຍທີ່ສຸດ.
  • ພວກເຮົາສາມາດກວດສອບດ້ວຍຕົນເອງໃນແຕ່ລະຄ່າໃນລະດັບ [min, max] ແຕ່ຍ້ອນວ່າຄ່າໃນລະດັບຖືກຈັດຮຽງດັ່ງນັ້ນພວກເຮົາຈະໃຊ້ ສູດການຄົ້ນຫາຖານສອງ ເພື່ອຄວາມສັບສົນໃນເວລາທີ່ດີກວ່າ.
  • ພວກເຮົາ ກຳ ລັງພະຍາຍາມຊອກຫາມູນຄ່ານ້ອຍທີ່ສຸດຂອງຕົວເລກດັ່ງນັ້ນວົງຈອນຈະສິ້ນສຸດລົງເມື່ອເລີ່ມຕົ້ນ <= ສິ້ນສຸດ. ໃນທີ່ສຸດ, ການເລີ່ມຕົ້ນຈະມີ ຄຳ ຕອບສຸດທ້າຍດັ່ງນັ້ນພວກເຮົາຈະສົ່ງຄືນຄ່າຂອງມັນ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບຊອກຫາວິທີການແບ່ງປັນຂະ ໜາດ ນ້ອຍທີ່ສຸດດ້ວຍວິທີແກ້ໄຂບັນຫາ Leetcode

#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

ລະຫັດ Java ສຳ ລັບຊອກຫາວິທີການແບ່ງປັນຂະ ໜາດ ນ້ອຍທີ່ສຸດດ້ວຍວິທີແກ້ໄຂບັນຫາ Leetcode

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) ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງຂີດ ຈຳ ນວນແຖວພຽງແຕ່ຄັ້ງດຽວ. ນີ້ n ແມ່ນຄວາມຍາວຂອງແຖວຕົວເລກ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ເພາະວ່າພວກເຮົາໃຊ້ ໜ່ວຍ ຄວາມ ຈຳ ເທົ່ານັ້ນທີ່ຈະເກັບ ຄຳ ຕອບ.

ເອກະສານ