对于数组[1,2,7,8,5] , 返回 [0,1,2,3,2]
解题思路:
题目提示我们使用线段树, 在这里我写了两种线段树的解法, 一种 TLE, 一种正常通过; 个人感觉两种写法需要因地制宜使用:
思路 1: 每个线段树节点存储的是原始 vector 的 index 前后值以及该区间内的相应最大值, 在查询时, 通过区域以及最大值约束找到所有小于特定值的区间最后求和.
class SegmentTreeNode { // 线段树节点, 其中 max 是当前区域内 (left-right) 最大值
- public: int start,
- end,
- max;
- SegmentTreeNode2 * left;
- SegmentTreeNode2 * right;
SegmentTreeNode2(int x, int y, int max) {
- this ->start = x;
- this ->end = y;
- this ->max = max;
- this ->left = this ->right = nullptr;
- }
- };
- class Solution {
- public:
- /**
- * @param A: an integer array
- * @return: A list of integers includes the index of the first number and the index of the last number
- */
- vector <int> countOfSmallerNumberII(vector <int> &A) {
- // write your code here
- auto tree = new SegmentTreeNode(0, A.size() - 1, INT_MIN);
- buildTree(A, tree);
- vector <int> ret;
- for (int i = 0; i <A.size(); ++i) {
- ret.push_back(query(tree, 0, i, A[i]));
- }
- return ret;
- }
int buildTree(vector < int> &A, SegmentTreeNode * root) { // 建立线段树, 每个节点保存该区域内最大值
- int start = root ->start;
- int end = root ->end;
- if (start> end) return 0;
- if (start == end) {
- root ->max = A[start];
- return A[start];
- } else {
- root ->left = new SegmentTreeNode(start, (start + end) / 2, INT_MIN);
- root ->right = new SegmentTreeNode((start + end) / 2 + 1, end, INT_MIN);
- int L_max = buildTree(A, root ->left);
- int R_max = buildTree(A, root ->right);
- root ->max = L_max> R_max ? L_max: R_max;
- return root ->max;
- };
- }
int query(SegmentTreeNode * root, int start, int end, int q) { // 查询特定区域比 q 小的个数
- if (root == nullptr) return 0;
- if (root ->start> end || root ->end <start) return 0;
- if (root ->start>= start && root ->end <= end && root ->max <q) return root ->end - root ->start + 1;
- return query(root ->left, start, end, q) + query(root ->right, start, end, q);
- }
- };
这种解法 TLE, 时间复杂度在 vector 的 size 很大时很大, 某种程度上来讲效率不及直接暴力法, 但当所求数据较为集中时应该能提高一点速度.
思路 2: 对数据的区间建立线段树, 在知道所有数据上界的情况下效率不错, 能够正常通过
class SegmentTreeNode { //count 表示当前区间所有的数个数
- public: int start,
- end,
- count;
- SegmentTreeNode * left;
- SegmentTreeNode * right;
SegmentTreeNode(int x, int y, int count) {
- this ->start = x;
- this ->end = y;
- this ->count = count;
- this ->left = this ->right = nullptr;
- }
- };
- class Solution {
- public:
- /**
- * @param A: an integer array
- * @return: A list of integers includes the index of the first number and the index of the last number
- */
- vector <int> countOfSmallerNumberII(vector <int> &A) {
- // write your code here
- vector <int> res;
- SegmentTreeNode * root = buildTree(0, 10001);
- for (int i = 0; i <A.size(); ++i) {
- res.push_back(query(root, A[i]));
- insert(root, A[i]);
- }
- return res;
- }
SegmentTreeNode * buildTree(int start, int end) { // 这种方法需要明确数据上界, 然后直接根据数据大小建立线段树, 每个节点保存落在当前区间数的个数
- if (start> end) return nullptr;
- auto res = new SegmentTreeNode(start, end, 0);
- if (start == end) return res;
- int mid = (start + end) / 2;
- res ->left = buildTree(start, mid);
- res ->right = buildTree(mid + 1, end);
- return res;
- }
int query(SegmentTreeNode * root, int q) { //query 函数用来查询当前区域内小于 q 的数的个数
- if (root == nullptr) return 0;
- if (q <root ->start) return 0;
- if (q> root ->end) return root ->count;
- return query(root ->left, q) + query(root ->right, q);
- }
- void insert(SegmentTreeNode * root, int val) { // 将输入数据逐个插入, 从上到下逐个更新 count
- if (root == nullptr) return;
- if (root ->start> val || root ->end <val) return;
- if (root ->start <= val && root ->end>= val)++root ->count;
- insert(root ->left, val);
- insert(root ->right, val);
- }
- }
ps: 这道题如果使用 lintcode 内置的 SegmentTreeNode 数据结构中的 count 好像会出问题, 最好定义自己的 class
来源: http://www.bubuko.com/infodetail-2552735.html