给定一个长度为 n 的非负整数数组 num ,和一个整数 m ,你需要把这个数组 num 分成 m 个非空连续子数组。
请你找出这些连续子数组各自的和的最大值最小的方案并输出这个值。
数据范围: , ,
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param num int整型一维数组 # @param m int整型 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/7a41720ebed04f37bb015febda6a75cb?tpId=196&tqId=40413&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 参考: 借鉴kjldvsdhv大神提交 算法: 题目要求将数组nums分割成n份,要求子数组累加和最大值尽可能小。 反向思考:我们以threshold将nums中的元素进行分割,如果恰好分割成m份,说明threshold就是所求解;否则,若分割结果大于m,说明threshold取小了;否则,说明threshold取大了。 threshold的取值范围:[max(nums), sum(nums)] 对于threshold的选取,这里我们采用二分查找的方式 复杂度: 时间复杂度:O(logD * N), D = sum(nums) - max(nums), N为数组nums的长度 空间复杂度:O(1) """ def splitMin(self, nums, m): def checkSplit(threshold): curSum, count = 0, 1 # 初始子数组累加和为0,数组未分割,只有1个区间 for num in nums: curSum += num if curSum > threshold: # 找到一个分割点,重置子数组累加和为num,子区间+1 count += 1 curSum = num return count > m left, right = max(nums), sum(nums) while left < right: mid = left + ((right - left) >> 1) if checkSplit(mid): # 以子数组和mid进行分割,得到的分割区间大于m,说明left取小了 left = mid + 1 else: right = mid return left if __name__ == "__main__": sol = Solution() nums, m = [1, 2, 3, 4, 5, 6], 3 res = sol.splitMin(nums, m) print res
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num int整型vector * @param m int整型 * @return int整型 */ int splitMin(vector<int>& num, int m) { int left = 0, right = 0; for (int i = 0; i < num.size(); i++) { left = max(left, num[i]); right += num[i]; } while (left < right) { int mid = left + (right - left) / 2; int cnt = 1, sum = 0; for (int i = 0; i < num.size(); i++) { if (sum + num[i] <= mid) { sum += num[i]; } else { cnt++; sum = num[i]; } } if (cnt <= m) { right = mid; } else { left = mid + 1; } } return left; } };