1、题目描述
https://leetcode-cn.com/problems/split-array-largest-sum/
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意: 数组长度 n 满足以下条件: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n)
输入: nums = [7,2,5,10,8] m = 2
输出: 18
解释: 一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8], 因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
2、代码详解
为什么要贪心地使子数组和不断逼近mid?
- 我先猜一个mid值,然后遍历数组划分,使每个子数组和都最接近mid(贪心地逼近mid),这样我得到的子数组数一定最少;
- 如果即使这样子数组数量仍旧多于m个,那么明显说明我mid猜小了,因此 lo = mid + 1;
- 而如果得到的子数组数量小于等于m个,那么我可能会想,mid是不是有可能更小?值得一试。因此 hi = mid;
class Solution(object):
def splitArray(self, nums, m):
# 由于题目的返回要求:返回最小和的值
# 最小和必然在 [max(nums), sum(nums)] 间
# 可以使用二分来进行查找
low, high = max(nums), sum(nums)
while low < high:
mid = (low + high) // 2
# 淘汰算法
# 数组分成 m 个非空的连续子数组
# 由前向后对nums进行划分,使其子数组和 <= mid,然后统计满足条件的数组数量
# 若我们选的sum值过小,则满足条件的数量 > m,目标值应落在 [mid+1, high]
# 若我们选的sum值过大,则满足条件的数量 < m,目标值应落在 [low, mid-1]
count = 0
sub_sum = 0
for i in range(len(nums)):
sub_sum += nums[i]
if sub_sum > mid:
count += 1
sub_sum = nums[i]
# 注意:末尾还有一个子数组我们没有统计,这里把它加上
count += 1
if count > m:
low = mid + 1
else:
high = mid
return low
nums = [7, 2, 5, 10, 8]
# # 分为[7,2,5] [10,8], 此时这两个子数组各自的和的最大值为18,在所有情况中最小。
m = 2
s = Solution()
print(s.splitArray(nums, m))
本文地址:https://blog.csdn.net/IOT_victor/article/details/107581397
如您对本文有疑问或者有任何想说的,请点击进行留言回复,万千网友为您解惑!
网友评论