摘要：我们建立的，其中解决重复值的问题，记录左子树的节点数。给定要找的点，这里的规律就是，往右下走，说明当前点和当前的的左子树的值全部比小。我们走到要向右，这是左子树没变化，这里也不变。
题目细节描述参看leetcode。
今天的重头戏 LC315 Count of Smaller Numbers After Self.
在讲这个题目之前，请思考这个问题。在BST找到所有比Node P小的节点个数。
利用inorder tarvseral我们一直走BST并计数，找到p点就返回计数得到的值。时间复杂度worst case O(n).如果我们要找到的是好多节点的值，如果还用这种方法，时间复杂度就是O(k*n).
这里我们有大量重复的工作，每次都从leftmost走，直到找到这个node Pi. 实际上我们可以预处理这个BST。把每个节点小于它的个数记录下来。综合的时间复杂度就是O(n+klogn).
要快速找到比自己小的数，就可以建立一个BST来帮助我们。
我们建立的Node(int val, int dup, int leftsum，Node left, Node right) 其中dup解决重复值的问题，leftsum记录左子树的节点数。
给一个[3,2,2,6,1]，构建出的树长这样，其中Node.val(dup, leftsum)表示每个节点。
1(1,0)
6(1,3)
/
2(2,0)
3(1,0)
建立的细节待会儿再讲。
假如我们的输入变为[5,3,2,2,6,1]要找比5小的怎么办？
首先1比5小，total = 1+0. 走到6发现比5大，去到2，发现5比2大，total += 2 +0。去到3，发现5比3大，total += 1+0, 最后total = 4.
假如我们的输入变为[7,3,2,2,6,1]要找比5小的怎么办？
首先1比7小，total = 1+0. 走到6发现比7发，total += 1+3， total = 5。
给定要找的点P，这里的规律就是，往右下走，说明当前点和当前的的左子树的值全部比P.val小。我们计数。
往左下走，我们不知道下面节点是否比p小，需要再重复上面的判断。直到找到所有比p小的节点数。
给定一个这样我们自定义的BST，我们直到如何找到。下面就是如何构造了。
还是上面那个图。我们加入5这个点，在走到6的时候，是走到6的左子树，这是6的左子树应该+1，变成：
1(1,0)
6(1,4)
/
2(2,0)
3(1,0)
5(1,0)
这是加入左子树的情况，现在再继续加入7这个点。我们走到6要向右，这是左子树没变化，6这里也不变。
和上面的例子稍有不同，我们连续加入了5，7这两个点。
1(1,0)
6(1,4)
/
2(2,0) 7(1,0)
3(1,0)
5(1,0)
我们可以试着返回小于7的节点数，也就是每次向右走的时候，node上的值求和。total = 1+0 + 1+4 = 6。
代码如下。
public class Solution {
class Node {
Node left, right;
int val, sum, dup = 1;
public Node(int v) {
val = v;
}
}
public List countSmaller(int[] nums) {
Integer[] ans = new Integer[nums.length];
Node root = null;
for (int i = nums.length - 1; i >= 0; i--) {
root = insert(nums[i], root, ans, i, 0);
}
return Arrays.asList(ans);
}
private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
if (node == null) {
node = new Node(num);
ans[i] = preSum;
} else if (node.val == num) {
node.dup++;
ans[i] = preSum + node.sum;
} else if (node.val > num) {
node.sum++;
node.left = insert(num, node.left, ans, i, preSum);
} else {
node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
}
return node;
}
}
代码来源： leetcode mayanist
https://discuss.leetcode.com/...
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/66573.html
摘要：当我们希望查询时，则从根节点开始寻找其所在的区间，如果位于左侧区间，则查询左子树啊，如果位于右侧区间，则查询右子树。如果横跨了分割点，则分别查询左子树的部分和右子树的部分。 题目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...
摘要：复杂度思路每遍历到一个数，就把他到已有的中。对于每一个，维护一个和一个自身的数目。比如，然后每次遍历到一个数，就把对应位置的值加一。比如碰到之后，就变成，然后统计的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...
摘要：题目链接的题，用来做，这种求有多少的题一般都是。里多加一个信息表示以为的节点数。也可以做，因为是统计有多少的，其实就是求从最小值到的。的是，要做一个映射，把的值映射到之间。所以先把给一下，用一个来做映射。还有的方法，参考 315. Count of Smaller Numbers After Self 题目链接：https://leetcode.com/problems... divi...
摘要：题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来，最后回原来正确的值。如果是叶子节点，或者只有一个子树。思想来自于的代码实现。 跳过总结请点这里：https://segmentfault.com/a/11... BST最明显的特点就是root.left.val < root.val < root.right.v...
Problem You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Exam...
阅读 1630·2021-10-12 10:11
阅读 3752·2021-09-03 10:35
阅读 1440·2019-08-30 15:55
阅读 2123·2019-08-30 15:54
阅读 994·2019-08-30 13:07
阅读 1006·2019-08-30 11:09
阅读 571·2019-08-29 13:21
阅读 2647·2019-08-29 11:32
