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 트리 구현입니다. 그것은 일을 끝내지 만 충분히 빠르지는 않습니다.
12 초에 100에서 48을 수행합니다.
===============
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 동안 100에서 84를 수행합니다.
=================
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);
}
=================
I 왜 그들이 목표를 달성하지 못하고 어떻게 향상시킬 수 있는지 이해하고 싶습니다.
이것은 codereview – mplungjan
에 속합니다. 빠른 컴퓨터에서 실행하십시오. – destoryer