• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?