会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
核心思路：按题面规则现建一棵 CART 二叉分类树。每个节点选一个特征和一个取值做二元切分，左子树放该特征等于这个取值的样本，右子树放不等于的样本。只有加权基尼指数比当前节点严格更小的切分才接受，否则停止。叶子预测人数更多的类别，两种人数相同就预测编号较小的 0。
实现方法：特征按编号从 1 到 4 枚举，每个特征里出现过的取值按从小到大枚举，基尼用分数比较，只有分子分母交叉相乘后严格变小才更新。这样平局会自然留下更小的特征编号和更小的取值。样本数小于 2，或者节点里只剩一种标签，也直接变成叶子。预测时从根往下走，测试样本的特征值等于切分值就进左子树，否则进右子树。
复杂度分析
特征个数是 4，一个节点里每个特征的不同取值不超过 4 种，都可以看成常数。每个节点只扫描自己的样本，而每个样本出现在从根到叶的一条链上，链长不超过 N，所以建树是 O(N2)。每个测试样本沿树向下，深度不超过 N，M 个样本是 O(NM)。节点数是 O(N)，空间 O(N)。本题 N≤20，M≤10，足够。
