填空题

等频离散化

Question

为了提高鲁棒性，连续特征在输入模型前，通常会通过“等频”离散化算子将连续特征转化成离散特征。“等频”离散化的定义如下：

给定从小到大已排序整数数组A，和划分段数K，“等频”离散化操作会将A划分成K个子集，且子集满足如下条件:

1. 子集之间没有重复元素
2. 在所有可能划分中，离散化输出的划分子集长度的方差最小

比如:

A=[1, 1, 2, 2], K=2，则[1, 1]，[2, 2]
是满足定义的划分（子集[1, 1]和[2, 2]之间没有重复元素），且方差为0、最小。
划分的平均长度E为(2+2)/2=2, 划分子集长度的方差为( (2-E)^2 + (2-E)^2 ) / 2 = ( (2-2)^2 + (2-2)^2 ) / 2 = 0。

A=[1, 1, 1,  2,  2 , 4,  5, 5], K=3, 侧可能的子集间没有重复元素的划分有:
（1）[1, 1, 1], [2, 2, 4], [5, 5]
（2）[1, 1, 1], [2, 2], [4, 5, 5]
（3）[1, 1, 1, 2, 2], [4], [5, 5]

其中（1）和(2)均是满足定义的划分，且方差为0.22、最小。以[1, 1, 1], [2, 2, 4], [5, 5]为例:
划分的平均长度E为(3+3+2)/3=8/3, 划分子集长度的方差为( (3-8/3)^2 + (3-8/3)^2 + (2-8/3)^2 ) / 3 = 0.22。

请设计算法，实现如上定义的“等频”离散化算子。

输入输出说明

- 输入: 整数数组A和划分K(整数)。A非空且长度小于65,535，A中的整数取值范围为[-32,768, 32,767]，K的长度范围为[1, 100]。A中必然存在至少K个不同的元素。

- 输出: 算子输出的划分。如果有满足约束的多组划分，输出任一组。