[Leetcode] 410. Split Array Largest Sum
上来就是一道Hard，不是我的本意，但是我在翻阅狗家面筋。虽然狗家不会要我这个渣，但是梦想还是要有的嘛，万一，见鬼了呢！本渣表示这道题看题用了一个小时，百度了好久，才看明白题目。。。感谢百度上各个大神的博客让我看懂了题。。。
题目：
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Note: If n is the length of array, assume the following constraints are satisfied: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n) Examples: Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
题目大意：
题目很简单，一个数组，让我们把这个数组切割成m个subarray，每个subarray求和，要使得这m个subarray里，和最大的array，和最小。换句话说，让我们最小化n个subarray中的
最大值。原谅我的翻译能力。。。题目链接在这里Leetcode401。
解题思路：
第一思路（本渣的第一思路，一定是最辣鸡的办法，没有之一），暴力破解法。但是，这个复杂度实在是太高了，高到我觉得至少是n方，这个编辑器n方怎么打也不知道。。。于是，我想也没想，就去看大神的解法了。最普遍的就是二分搜索。以前一直以为二分搜索是用来搜索有序数组的，今天才知道还有这个巧妙的用处。值得注意的是呢，这个方法有用依赖于题目中的一个条件，数组里的每个数都是non-negative integers。也就是说，我们每将一个数放到subarray里，这个subarray的和就变大了，而不会减小。
这个二分法不一样的地方是，它不是二分数组，而是二分这个和（sum），用sum比较有助于理解，我们下面就都用sum了。既然是二分法，就要有一个上下界[low，high]。这里，我们这个sum的最小值，是数组中最大的一个数，如果数组长度是n的话，我们把数组分成n份，这时候，每个element就是一份，这时，返回数组中最大数字即可。如果m是1，那整个数组就是个子数组，返回nums所有元素之和。所以对于其他有效m值，返回值一定在以上两个值之间，于是我们得到我们的上下界[Max(nums[i])，Sum(nums[i])]。
举个栗子，nums = [1,2,3,4,5], m=3. low = 5，high = 15.这时候，中间值mid是10。mid是我们要返回的结果的化身，我们通过不断调整low和high来调整mid，就像正宗的给数组二分查找一样。接下来是要找出sum最大，且sum小于等于mid的subarray的个数，[1,2,3,4]，[5], 可以发现，根本无法分成3组，说明我们mid定的太大了，缩小mid，我们就能把数字多的subarray里的数“挤”出来，缩小到多少呢，我们二分法就起作用了，我们调整右边界，让high = mid，然后我们再次进行二分查找，mid = 7，要找到sum最大，且sum小于等于7的subarray的个数，[1,2,3],[4],[5]. 成功找出了3组，说明mid还有可降低的空间。继续让high = mid。这时mid = 6，要找到sum最大，且sum小于7的subarray的个数，[1,2,3],[4],[5].再次二分查找，算出mid = 5，再次找出和最大且小于等于5的子数组的个数，[1,2], [3], [4], [5]，发现有4组，此时我们的mid太小了，应该增大mid。让下边界low = mid+1，此时，low = 6， high = 5，循环退出了，我们返回low即可。如果循环没退出我们继续。
复杂度的话nlog(n)，二分查找嘛，这个事平均的当然，最坏的也是n方应该，这个不确定，欢迎批评指正啊，本渣感激不尽，临表涕零。
AC答案：
下面这个答案来自 Discussion
public class Solution {
/**
* 这个数肯定介于最大的那一个单值和所有元素只和的中间
* */
public int splitArray(int[] nums, int m) {
long sum = 0;
int max = 0;
for(int num: nums){
max = Math.max(max, num);
sum += num;
}
return (int)binarySearch(nums, m, sum, max);
}
//二分查找
private long binarySearch(int[] nums, int m, long high, long low){
long mid = 0;
while(low < high){
mid = (high + low)/2;
//验证是否满足,也就是这么大的值有可能出现么
if(valid(nums, m, mid)){
high = mid;
}else{
low = mid + 1;
}
}
return high;
}
/**
* 验证这个值是否合法
* */
private boolean valid(int[] nums, int m, long max){
int cur = 0;
int count = 1;
//是否有多于m个片段or区间，大于给定值的max的，如果有了，那么就不合法了，因为这样划分就不止m个，即max太小
for(int num: nums){
cur += num;
if(cur > max){
cur = num;
count++;
if(count > m){
return false;
}
}
}
return true;
}
}
好了今天先写到这。One more thing，这个题解题的关键在于：二分查找，确定上下界，移动mid，算subarray个数，个数小了没事，缩小mid，把数从数组里“挤”出来；数组多了，增大mid，把多的数放回去，一旦能放回去，而且数组个数刚好了，ok，结束战斗！
只要subarray不多，就缩小mid，直到low比high大
Comments
Post a Comment