最小方差划分

给一个数组,求一个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 条评论
登录 后参与评论

相关文章

来自专栏郭耀华‘s Blog

TensorFlow 常用函数汇总

82620
来自专栏数据处理

TensorFlow入门1-minist

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

27:单词翻转

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

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

洛谷P1887 乘积最大3

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

36980
来自专栏杂七杂八

matlab中的函数介绍(max,min,unidrnd,norm)

遇到不知道的函数时,可以使用help 函数名来查看帮助 1 求矩阵A的最大值的函数有3种调用格式,分别是: max(A):返回一个行向量,向量的第i个元...

42450
来自专栏AI派

Numpy 修炼之道 (7)—— 形状操作

无论是ravel、reshape、T,它们都不会更改原有的数组形状,都是返回一个新的数组。

30230
来自专栏偏前端工程师的驿站

代数几何:点,线,抛物线,圆,球,弧度和角度

一, 笛卡尔坐标系                         ? 笛卡尔坐标系是数学中的坐标系,而计算机中则采用屏幕坐标系统. ? 而三维坐标系则没有一个...

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

【每日一题】

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

11120
来自专栏fangyangcoder

leetcode(三)

给定一个二维的矩阵(矩阵的数全由1和0组成),任意反转矩阵的每一行和每一列(0反转成1,1反转成0),求出最大矩阵分数,矩阵分数的求法是矩阵每一行代表二进制数,...

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

单调栈小结

18010

扫码关注云+社区

领取腾讯云代金券