0
该数组包含数字并且未排序。它的长度可能大到100000. 我需要计算每个数字右侧的较小数字。如何让此代码更快运行
例子：
100, 10, 10, 10, 10]should return 4, 0, 0, 0, 0
1, 2, 3 should return 0, 0, 0
1, 2, 0 should return 1, 1, 0
1, 2, 1 should return 0, 1, 0
任务：我有100个项目执行，目标是做他们全部下为12ms。 以下函数是AVL树的实现。它完成了工作，但速度不够快。
它在12s中执行48中的100个。
===============
function smaller(arr) {
function TreeNode(key) {
this.key = key;
this.size = 1;
this.height = 1;
this.left = null;
this.right = null;
this.count = 1;
}
var size = (node) => node == null ? 0 : node.size + node.count - 1;
var height = (node) => node == null ? 0 : node.height;
var getBalance = (node) => node == null ? 0 : height(node.left) - height(node.right);
var rotateRight = function(root) {
var newRoot = root.left;
var rightSubTree = newRoot.right;
newRoot.right = root;
root.left = rightSubTree;
root.height = Math.max(height(root.left), height(root.right)) + 1;
newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1;
root.size = size(root.left) + size(root.right) + 1;
newRoot.size = size(newRoot.left) + size(newRoot.right) + 1;
return newRoot;
}
var rotateLeft = function(root) {
var newRoot = root.right;
var leftSubTree = newRoot.left;
newRoot.left = root;
root.right = leftSubTree;
root.height = Math.max(height(root.left), height(root.right)) + 1;
newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1;
root.size = size(root.left) + size(root.right) + 1;
newRoot.size = size(newRoot.left) + size(newRoot.right) + 1;
return newRoot;
}
var insertIntoAVL = function(node, key, count, index) {
if(node == null)return new TreeNode(key);
if(key < node.key){node.left = insertIntoAVL(node.left, key, count, index);}
if(key == node.key){count[index] = count[index] + size(node.left); node.count++; return node;}
if(key > node.key){node.right = insertIntoAVL(node.right, key, count, index); count[index] = count[index] + size(node.left) + node.count;}
node.height = Math.max(height(node.left), height(node.right)) + 1;
node.size = size(node.left) + size(node.right) + 1;
var balance = getBalance(node);
if(balance > 1 && key < node.left.key){return rotateRight(node);}
if(balance < -1 && key > node.right.key){return rotateLeft(node);}
if(balance > 1 && key > node.left.key){node.left = rotateLeft(node.left); return rotateRight(node);}
if(balance < -1 && key < node.right.key){node.right = rotateRight(node.right); return rotateLeft(node);}
return node;
}
var countSmallerOnRight = function(arr) {
var result = new Array(arr.length).fill(0);
var root = null;
for (var i = arr.length; i--;){root = insertIntoAVL(root, arr[i], result, i);}
return result;
}
return countSmallerOnRight(arr);
}
=================
我有一个第二种方法虽然速度更快但仍不够快。 它在12ms内执行84次中的100次;
=================
function smaller(arr) {
function BSTNode(val, count) {
this.dup = 1;
this.left = null;
this.right = null;
this.val = val;
this.count = count;
}
var countSmaller = arr => {
var result = [];
var root = null;
for (var i = arr.length; i--;){root = insert(root, arr[i], result, 0, i);}
return result;
}
var insert = (root, num, result, sum, i) => {
if (root == null) {
root = new BSTNode(num, 0);
result[i] = sum;
return root;
} else if (root.val == num) {
root.dup++;
result[i] = sum + root.count;
return root;
} else if (root.val > num) {
root.count++;
root.left = insert(root.left, num, result, sum, i);
} else {
root.right = insert(root.right, num, result, sum + root.count + root.dup, i);
}
return root;
}
return countSmaller(arr);
}
=================
我想了解为什么他们没有达到目标，我该如何改进他们。
这属于codereview – mplungjan
在更快的机器上运行它。 – destoryer