华为OD统一考试 - 结队编程

题目描述

某部门计划通过结队编程来进行项目开发，

已知该部门有 N 名员工，每个员工有独一无二的职级，每三个员工形成一个小组进行结队编程，结队分组规则如下：

从部门中选出序号分别为 i、j、k 的3名员工，他们的职级分贝为 level[i]，level[j]，level[k]，

结队小组满足 level[i] < level[j] < level[k] 或者 level[i] > level[j] > level[k]，

其中 0 ≤ i < j < k < n。

请你按上述条件计算可能组合的小组数量。同一员工可以参加多个小组。

输入描述

第一行输入：员工总数 n

第二行输入：按序号依次排列的员工的职级 level，中间用空格隔开

限制：

• 1 ≤ n ≤ 6000
• 1 ≤ level[i] ≤ 10^5

输出描述

可能结队的小组数量

用例

题目解析

本题的意思其实就是让我们求解给定输入数组中，比如用例1中 [1,2,3,4] ，每个数组元素：

• 左边比自己大的元素的个数，设为：leftBiggerCount
• 左边比自己小的元素的个数，设为：leftSmallerCount
• 右边比自己大的元素的个数，设为：rightBiggerCount
• 右边比自己小的元素是的个数，设为：rightSmallerCount

当我们求解出每个数组元素的上述信息后，累加每个数组元素的如下计算结果：

leftBiggerCount * rightSmallerCount + leftSmallerCount * rightBiggerCount

比如题目用例1中，数组 [1,2,3,4]，索引为 idx

• idx=0元素，leftBiggerCount = 0，leftSmallerCount = 0，rightBiggerCount = 3，rightSmallerCount = 0leftBiggerCount * rightSmallerCount + leftSmallerCount * rightBiggerCount = 0
• idx=1元素，leftBiggerCount = 0，leftSmallerCount = 1，rightBiggerCount = 2，rightSmallerCount = 0leftBiggerCount * rightSmallerCount + leftSmallerCount * rightBiggerCount = 2
• idx=2元素，leftBiggerCount = 0，leftSmallerCount = 2，rightBiggerCount = 1，rightSmallerCount = 0leftBiggerCount * rightSmallerCount + leftSmallerCount * rightBiggerCount = 2
• idx=3元素，leftBiggerCount = 0，leftSmallerCount = 3，rightBiggerCount = 0，rightSmallerCount = 0leftBiggerCount * rightSmallerCount + leftSmallerCount * rightBiggerCount = 0

因此数组[1,2,3,4]的结队编程数量为4。

二叉搜索树解法

本题更优策略可以使用二叉搜索树，将时间复杂度降到O(NlogN)。

二叉搜索树，也叫二叉排序树，特点是其中序遍历序列是有序的。而构建二叉搜索树的步骤很简单，每次向二叉搜索树加入新节点时，都去和遇到的（子树）根节点进行比较：

• 如果 新节点的值 < 根节点的值，则插入到根节点的左子树中，然后继续递归和左子树根比较
• 如果 新节点的值 > 根节点的值，则插入到根节点的右子树中，然后继续递归和右子树根比较

因此，二叉搜索树中每个节点的左子树中所有节点的值都比自己小，右子树中所有节点的值都比自己大。

那么如何利用二叉搜索树解决本题呢？这里我通过图示说明。

首先我们来定义出二叉搜索树节点结构：

这里的二叉搜索树节点和数组元素是互相关联的。

然后，我们需要按照输入数组的倒序取元素插入到二叉搜索树中（PS：原因后面说明）

由于题目用例太极端，这里我自己建一个 [3, 1, 7, 2, 8, 6, 4 , 9, 5]

[3, 1, 7, 2, 8, 6, 4 , 9, 5]

插入5

[3, 1, 7, 2, 8, 6, 4 , 9, 5]

插入9

[3, 1, 7, 2, 8, 6, 4, 9, 5]

插入4

[3, 1, 7, 2, 8, 6, 4 , 9, 5]

插入6

[3, 1, 7, 2, 8, 6, 4 , 9, 5]

插入8

[3, 1, 7, 2, 8, 6, 4 , 9, 5]

插入2

后面就不画了，大家可以自己继续往下推导。

总结一下，插入新节点到二叉搜索树中，新节点需要不断和各种子树的根进行比较：

• 如果新节点的值 < 根节点的值，则Node(根).leftChildCount++新节点递归进入根的左子树，继续比较
• 如果新节点的值 > 根节点的值，则Node(新).rightSmallerCount新节点递归进入根的右子树，继续比较