arrays - 有没有更优雅的方式来做到这一点？

Question

给定一个正整数数组 a 我想输出整数数组 b 以便 b[i] 是最接近的数字a[i] 比 a[i] 小，并且在 {a[0], ... a[i-1]} 中。如果这样的数字不存在，则 b[i] = -1。

例子:

a =  2  1 7 5 7 9b = -1 -1 2 2 5 7

b[0] = -1 因为没有小于 2 的数
b[1] = -1 因为 {2}
中没有小于 1 的数字b[2] = 2，{2,1} 中小于 7 的最接近 7 的数是 2
b[3] = 2，{2,1,7} 中小于 5 的最接近 5 的数是 2
b[4] = 5，{2,1,7,5} 中小于 7 的最接近 7 的数是 5

我正在考虑实现平衡二叉树，但它需要大量工作。有更简单的方法吗？

Answer 1

这是一种方法:

 for i ← 1 to i ← (length(A)-1) {
     // A[i] is added in the sorted sequence A[0, .. i-1] save A[i] to make a hole at index j
     item = A[i]
     j = i

     // keep moving the hole to next smaller index until A[j - 1] is <= item
     while j > 0 and A[j - 1] > item {
         A[j] = A[j - 1]  // move hole to next smaller index
         j = j - 1
       }

     A[j] = item  // put item in the hole

     // if there are elements to the left of A[j] in sorted sequence A[0, .. i-1], then store it in b
     // TODO : run loop so that duplicate entries wont hamper results
     if j > 1
        b[i] = A[j-1]
     else 
        b[1] = -1;
   }

试运行:

a =  2 1 7 5 7 9
a[1] = 2

很简单，将b[1]设置为-1

a[2] = 1

插入子数组:[1 ,2]排序数组中 1 之前的任何元素？不。所以将 b[2] 设置为 -1 。 b: [-1, -1]

a[3] = 7

插入子数组:[1 ,2, 7]排序数组中 7 之前的任何元素？是的。它的 2所以将 b[3] 设置为 2。 b: [-1, -1, 2]

a[4] = 5

插入子数组:[1 ,2, 5, 7]排序数组中 5 之前的任何元素？是的。它的 2所以将 b[4] 设置为 2。 b: [-1, -1, 2, 2]

等等..