javascript - 给出一个原始数组和一个新数组，每个元素的值表示左边更大的元素的数量

Question

给定一个数组，比如[4,2,1,3,5]，基于这个数组，我们有一个新数组，其中每个数字表示其左侧大于自身的元素的数量，即[0,1,2,1,0]。现在编写一个给定输入 [0,1,2,1,0] 的函数，返回原始数组。数组的范围是1~n(n是数组的大小，排序后可以假设原数组中的所有数字都是连续的)

现在为了恢复原始数组，我尝试了一种通过从末尾到前面遍历数组范围来解决问题的方法，如下所示:

我的方法:

假设范围是 1 ~ 5，如果排序，原始数组将是 [1, 2, 3, 4, 5]。从末尾迭代到beg，

所以第一个 5，没有元素可以大于 5，所以它的更大元素的最大数量为 0，然后 4 的更大元素的最大数量为 1，3 到 2，等等。存储 key -值对成一个对象。

现在从后到前遍历输入，

1. 0 -> 5
2. 1 -> 可以是 4、3 或 2
3. 2 -> 可以是 3、2 或 1
4. 1 -> 任何大于第一个的数字。
5. 0 ->(可以是任何值，因为取了 5，所以它可以是 1、2、3 或 4)

仅仅将输入的每个元素作为值映射到映射中的键是不够的。以最佳性能解决此问题的直观方法是什么？ (尽可能避免 O(n ^2)。)

Answer 1

最初从数字 1 到 n 制作一个 AVL 树。

从后面开始，即第 n 个索引(考虑基于 1 的索引)。

现在算法的高级概要级别应该如下所示:

1. At any ith index, say the number in array(not the originial array) is j
2. Search the number which is at (i-j)th position in your AVL tree(This can be done in O(logn) time. Comment if you need more explanation on this)
3. The element in the AVL tree is your required element. Delete that element from AVL tree.(O(logn))

因此总复杂度为 O(nlogn)。

演练

最初树将包含所有 5 个元素。

1. 您从索引 5(基于 1 的索引)开始。元素为0，即i=5，j=0。所以第 5 大元素是 5。

2. 现在树包含四个元素 1、2、3 和 4。i=4，j=1。所以 4-1 即 3rd 最大元素，在这种情况下为 3。

3. i=3，j=2。 (3-2)rd 最大元素是 1，因为树包含 (1, 2, 4)。

等等。

用树求第i大数

我们可以通过将左子树中的节点数存储在根节点处来实现。所以考虑一棵树，具有元素 1、2、3、4 和 5，树结构如下:

        4(3)
      /     \
     3(1)   5(0)
     /   \
    1(0)  2(0)

在根节点，数字 4 是值，圆括号中的数字表示左子树中的节点数。

在构建(插入和删除)树时，我们可以维护计数。

现在，要找到第 i 个节点，假设我们想要假设给定树中的第 3 个节点。我们从根开始，它说它左边有 3 个比它小的元素，所以我们向左移动。现在根即 3 有 1 个较小的左边元素，它小于 3(第 ith 个元素)所以我们移动到它的右边。从 3 中减去 1(左计数)+1(根本身)。现在根是 2，我们想要第一个元素，左计数是 0。因此以 2 为根的子树的第一个元素是 2。

基本伪代码如下:

while(true){
  count  = root->leftCount;
  if((count+1)<i){
     //move to right
     i-=(count+1);
     root = root->right;
  }
  else if(i==(count+1)){
     //root is the ith node
     break;
  } else{
     //move to the levft
     root=root->left

  }
}