最小方差划分
给一个数组，求一个k值，使得前k个数的方差 + 后面n-k个数的方差最小
解题思路：
如果不考虑方差的概念，这题可以简化为 “给一个数组，求一个k值，使得前k个数的和 + 后面n-k个数的和最小”。
举例， 如 nums = [1,3,2,4]，我们可以先从左向右求出各个子段和 [1,4,6,10]，然后再从右向左求出各个子段和 [4,6,9,10]，我们发现对应的子段和为 1 -> 9, 4 -> 6, 6 -> 4。因此，我们只需要正反遍历数组两次，就可以求得结果。
时间复杂度：O(n)，空间复杂度 O(n)
方差概念：平方的均值减去均值的平方，即 D(X) = E(x^2) - [E(X)]^2
Python 实现：
class Solution:
"""
@param nums: 数组
@return: 最小方差划分的数组索引和最小方差
"""
def minVariancePartition(self, nums):
left = self.subVariance(nums[:])
right = self.subVariance(nums[::-1])[::-1]
minVariance, index = float("inf"), 0
for i in range(1, len(right)):
if left[i-1] + right[i] < minVariance:
minVariance = left[i-1] + right[i]
index = i - 1 # 更新划分的索引
return index, minVariance
def subVariance(self, nums):
subVar = []
subSum = subSquare = 0
for i in range(len(nums)):
subSum += nums[i]
subSquare += nums[i] * nums[i]
subVar.append(subSquare/(i+1) - (subSum/(i+1))**2) # 子数组方差
return subVar
a = [4,3,1,2]
print(Solution().minVariancePartition(a)) # (1,1.25)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录