最小方差划分

给一个数组,求一个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)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 数值的整数次方 [剑指offer] 数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

743
来自专栏数据结构与算法

27:单词翻转

27:单词翻转 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个句子(一行),将句子中的每一个单词翻转后输出。 输入只有一行,为一个...

3977
来自专栏数据结构与算法

单调栈小结

1671
来自专栏余林丰

9.动态规划(2)——子集和问题

注:因为对“子集和问题”的学习不够深入,所以本文在讲解动态规划递推公式中可能存在叙述不清,或者错误的地方,如有发现望能不吝赐教。   子集和问题可描述如下:给定...

3218
来自专栏专知

【干货】计算机视觉实战系列03——用Python做图像处理

【导读】专知成员Hui上一次为大家介绍Matplotlib的使用,包括绘图,绘制点和线,以及图像的轮廓和直方图,这一次为大家详细讲解Numpy工具包中的各种工具...

44510
来自专栏数据结构与算法

洛谷P1887 乘积最大3

题目描述 请你找出M个和为N的正整数,他们的乘积要尽可能的大。 输出字典序最小的一种方案。 输入输出格式 输入格式: 一行,两个正整数N,M 输出格式: M个...

3418
来自专栏Python小屋

Python标准库random用法精要

random标准库主要提供了伪随机数生成函数和相关的类,同时也提供了SystemRandom类(也可以直接使用os.urandom()函数)来支持生成加密级别要...

2926
来自专栏C语言及其他语言

【每日一题】

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大! 这种方法的具体描述如下:...

1072
来自专栏magicsoar

动态规划(dynamic programming)

动态规划的基本思想 动态规划的基本思想在于发现和定义问题中的子问题,这里子问题可也以叫做状态;以及一个子问题到下一个子问题之间 是如何转化的 也就是状态转移方程...

3245
来自专栏趣学算法

数据结构 第9讲 数组与广义表

LOC(a00)表示第一个元素的存储位置,即基地址,LOC(aij)表示aij的存储位置。 授人以鱼不如授人以渔,告诉你记住公式,就像送你一条鱼,不如交给你捕...

1192

扫码关注云+社区