315.计算右侧小于当前元素的个数
image
解题思路
- 暴力破解,两层for循环嵌套,
O(n^2)
最后测试会超时,需要优化。
- 方法1:使用
BST
(二叉搜索/排序数)
BST
(二叉搜索/排序数) Java代码
class Solution {
// 采用二叉搜索的做法,在树节点除了有val值外,还有个count值,用于记录它的左子树上有多少个节点
// 这样,最开始那个点形成的树节点,count值是0
public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new ArrayList<>();
if (nums == null || nums.length <= 0) return list;
int[] ret = new int[nums.length];
TreeNode root = null;
for (int i = nums.length - 1; i >= 0; i--) {
root = insert(root, new TreeNode(nums[i]), ret, i);
}
for (int n : ret) {
list.add(n);
}
return list;
}
/**
* 插入到树里面的时候,还需要更小count域的值。
* @param root 根节点
* @param node 待插入的节点
* @param ret 当node插入到树之后,实际上它的ret已经是确定的来
* @param i 数组下标
*/
public TreeNode insert(TreeNode root, TreeNode node, int[] ret, int i) {
if (root == null) {
root = node;
return root;
}
// 如果待插入的数比较小,或者相等的时候,就往左子数中插入,且根节点的count加1
if(node.val <= root.val) {
root.count++;
root.left = insert(root.left, node, ret, i);
} else {
// 对应点的count增加越过的那个节点的count值 + 1。因为越过的那个节点也比它小
ret[i] += root.count + 1;
root.right = insert(root.right, node, ret, i);
}
return root;
}
// 树节点中除了val,还有个count,来统计它的左子树的节点
class TreeNode {
int val;
int count;
TreeNode left;
TreeNode right;
public TreeNode(int value) {
this.val = value;
this.count = 0;
this.left = null;
this.right = null;
}
}
}
部分图片来源于网络,版权归原作者,侵删。
网友评论