SHARE
TWEET

Untitled

a guest Jun 17th, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution(object):
  2.  
  3.     def __init__(self, nums, m):
  4.         self.nums = nums
  5.         self.m = m
  6.     def split_array(self, nums, m):
  7.         """
  8.         :type nums: List[int]
  9.         :type m: int
  10.         :rtype: int
  11.         """
  12.         min_res = max(nums)
  13.         max_res = sum(nums)
  14.         low, high = min_res, max_res
  15.         while low + 1 < high:
  16.             mid = low + (high - low)//2
  17.             if self.is_valid(nums, m, mid):
  18.                 high = mid
  19.             else:
  20.                 low = mid
  21.         if self.is_valid(nums, m, low):
  22.             return low
  23.         return high
  24.  
  25.     def is_valid(self, nums, m, n):
  26.         count, current = 1, 0
  27.         for i in range(len(nums)):
  28.             if nums[i] > n:
  29.                 return False
  30.             current += nums[i]
  31.             if current > n:
  32.                 current = nums[i]
  33.                 count += 1
  34.         if count > m:
  35.             return False
  36.         return True
  37.      
  38. output = Solution([7,2,5,10,8], 2)
  39. print(output.split_array([7,2,5,10,8], 2))
  40. >>> 18
  41.      
  42. %timeit output.split_array([7,2,5,10,8], 2)
  43. 12.7 µs ± 512 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  44.      
  45. def __init__(self, nums, m):
  46.     self.nums = nums
  47.     self.m = m
  48.      
  49. def is_valid(self, nums, m, n):
  50.      
  51. def is_valid(self):
  52.      
  53. for i in range(len(nums)):
  54.      
  55. for num in nums:
  56.      
  57. if nums[i] > n:
  58.     return False
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top