困难-线段树-计算右侧小于当前元素的个数


by: funco 林鸿钊

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

问题来源

leetcode 315. 计算右侧小于当前元素的个数

问题解决

首先说明一下，这道题的解法有很多，
包括时间复杂度为O(n^2)的暴力破解，以及归并排序、二叉搜索树（二分查找）、二分查找。
这里主要对二叉搜索树方法进行介绍。

二叉搜索树（线段树思想）

假设每个元素的值作为节点的关键字，从列表头部开始遍历，构建二叉树。
第一个元素作为根节点，后续节点插入从根节点开始遍历树，小于当前元素值则进入左子树，大于当前元素值则进入右子树。
直到遍历至叶子节点时，相应作为当前叶子节点的左节点或右节点。

题解

以下序列为例

1
3, 76, 99, 51, 9, 21, 84, 66, 65, 36, 100, 41

此时，定一个二叉树节点，具有一下属性

字段 含义
value 当前节点对应元素值
smaller 比当前节点value值小的数量
dup 重复数量，取默认值为1
left 指向左子树根节点
right 指向右子树根节点

上述序列从后向前遍历，此时，最后一个节点为根节点，每获取前一个元素，就新增一个节点*new。
新节点new从根节点开始遍历比较，比当前节点cur->value小，则进入左子树，并在当前节点中记录cur->smaller++，
大于当前节点，则进入右子树且记录count数组count[NEW_FIX] += cur->smaller + cur->dup，
等于当前节点则记录cur->dup++。

遍历至叶子节点后，记录新节点new为当前节点cur的左节点或右节点。
当前元素插入二叉树后，将当前节点cur->smaller插入count数组。
遍历完成后，count数组即为最终结果。

遍历至元素36时，得到树结构和统计数组如下。

图片

遍历完成后，得到的树结构和统计数组如下

图片

分析上述构建过程和最后的计算过程可知，二叉树的构建和数组统计同步进行，因此时间复杂度取决于元素数量n，以及搜索过程中经过的节点数量（最坏情况为n，最好情况为logn）。因此，时间复杂度为O(nlogn)。

代码

惯例，上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>

using namespace std;

typedef struct Node
{
	int val = 0;// 当前值
	int smallCount = 0;// 比当前值小的数量
	int dupCount = 1;// 重复数量

	struct Node* left = NULL,*right = NULL;
}Node;

class Solution {

public:
    vector<int> countSmaller(vector<int>& nums) {
		int num = 0, fix = nums.size() - 1;
		vector<int> counts(nums.size(), 0);// 初始化结果数组

		// 没有元素或只有一个元素时无需统计直接返回
		if (fix <= 0) {
			return counts;
		}

		Node last;
	    last.val = nums[fix--];
		Node *root = &last;
		Node *cur = NULL;// 遍历节点指针
		Node *newNode = NULL;// 新节点指针

		while (fix >= 0) {
			newNode = new Node;// 初始化新节点
			newNode->val = nums[fix];

			// 搜索
			cur = root;// 从根节点开始
			while (1) {
				if (cur->val >= newNode->val) {
					cur->smallCount++;
					if (cur->left) {
						cur = cur->left;
					} else {
						cur->left = newNode;
						break;
					}
				} else {
					counts[fix] += cur->smallCount + cur->dupCount;
					if (cur->right) {
						cur = cur->right;
					} else {
						cur->right = newNode;
						break;
					}
				}
			}

			fix--;
		}

		return counts;
	}
};

难点与小结

求区间关系，首先想到线段树和树状数组两种方法，不管用哪种方法，首先需要的是理清过程变化以及如何记录结果值的问题。
以此题为例，个人认为该题难点主要在于如何更新新节点的smallCount，我一开始思路受限于搜索过程中就更新smallCount，
导致每次遍历仅有前三个节点统计正确，之后的数就全乱了，原因是每次搜索的时候右子树上一节点的smallCount与当前节点的
smallCount 统计存在交叉的地方。理了好久，突然想到，smallCount仅作为其左子树节点的数量，实际统计值直接放在结果数组中，
然后如上处理，即可保证统计结果正确。

Sub

扫码关注微信公众号，随时随地，掌握最新技术资讯

微信

Gitalking ...