给定一个正整数数组，a我想输出整数数组，b这样b[i]最接近的数字a[i]就小了a[i]，并且在{a[0], ... a[i-1]}. 如果这样的数字不存在，那么b[i] = -1.
例子：
a = 2 1 7 5 7 9 b = -1 -1 2 2 5 7
b[0] = -1因为没有小于 2
b[1] = -1的数字 因为没有小于 1 的数字 from {2}
b[2] = 2，最接近的数字 7 小于 7 from{2,1}是 2
b[3] = 2，最接近的数字 5 小于 5 from{2,1,7}是 2
b[4] = 5，最接近的数字到小于 7 的 7 from{2,1,7,5}是 5
我正在考虑实现平衡二叉树，但是这需要很多工作。有没有更简单的方法来做到这一点？
这是一种方法：
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]
等等..
您可以将其视为插入排序。
伪代码：
let arr be one array with enough space for every item in a
let b be another array with, again, enough space for all elements in a
For each item in a:
perform insertion sort on item into arr
After performing the insertion, if there exists a number to the left, append that to b.
Otherwise, append -1 to b
return b
您必须担心的主要事情是确保您不会犯重新分配数组的错误（因为它会重新分配 n 次，这将非常昂贵）。这将是您使用的任何语言的实现细节（std::vector 为 C++ 保留 ... arr.reserve(n) 为 D ... ArrayList 在 Java 中的 ensureCapacity ...）
与使用二叉树相比，这种方法的一个潜在缺点是它的时间为 O(n^2)。但是，使用这种方法与二叉树相比，使用这种方法的常数因子会使较小的尺寸更快。如果您的 n 小于 1000，这将是一个合适的解决方案。但是，O(n log n) 的增长速度比 O(n^2) 慢得多，因此如果您预计 a 的大小会明显更高，并且您可能会违反时间限制，您可能会考虑更复杂的 O( n log n) 算法。
有一些方法可以稍微提高性能（例如使用二进制插入排序：使用二进制搜索来查找要插入的位置），但通常在大多数情况下它们不会提高性能，因为它仍然是 O(n^ 2) 时间转移元素以适应。
这是一个（几乎）O（n log n）算法的草图，它介于实现插入排序和平衡二叉树的难度之间：向后做问题，使用合并/快速排序，并使用二分搜索。
伪代码：
let c be a copy of a
let b be an array sized the same as a
sort c using an O(n log n) algorithm
for i from a.length-1 to 1
binary search over c for key a[i] // O(log n) time
remove the item found // Could take O(n) time
if there exists an item to the left of that position, b[i] = that item
otherwise, b[i] = -1
b[0] = -1
return b
有一些实现细节会使它的运行时间很差。
例如，由于您必须删除项目，因此在常规数组上执行此操作并四处移动将使该算法仍然需要 O(n^2) 时间。因此，您可以改为存储键值对。一个是键，另一个是这些键的数量（有点像在数组上实现的多重集）。“删除”一个只是从一对中减去第二个项目，依此类推。
最终你会留下一堆 0 值的键。这最终将if there exists an item to the left花费大约 O(n) 时间，因此，整个算法将因此降级为 O(n^2)。所以另一个优化可能是定期批量删除它们。例如，当其中 1/2 是 0 值时，执行修剪。
理想的选择可能是实现另一个具有更有利的删除时间的数据结构。类似于带有索引的修改展开链表的方法可以工作，但它肯定会增加这种方法的实现复杂性。
我实际上已经实现了这一点。我使用了上面的前两个优化（存储键值对进行压缩，并在其中 1/2 为 0 时进行修剪）。以下是一些使用插入排序导数与此比较的基准：
a.length 这个方法插入排序方法 100 0.0262ms 0.0204ms 1000 0.2300ms 0.8793ms 10000 2.7303ms 75.7155ms 100000 32.6601 毫秒 7740.36 毫秒 300000 98.9956 毫秒 69523.6 毫秒 1000000 333.501 毫秒 ????? 不够耐心
所以，正如你所看到的，这个算法的增长速度比我之前发布的插入排序方法慢得多。但是，插入排序方法需要 73 行代码，而 26 行代码。因此，就简单性而言，如果您没有时间要求/输入很小，插入排序方法可能仍然是可行的方法。
考虑一下：
a = 2 1 7 5 7 9
b = -1 -1 2 2 5 7
c 0 1 2 3 4 5 6 7 8 9
0 - - - - - - - - - -
其中 C 的索引是 a[i] 的值，这样 0,3,4,6,8 将具有空值。
并且 C 的第一维包含迄今为止最接近 a[i] 的值
So in step by a[3] we have the following
c 0 1 2 3 4 5 6 7 8 9
0 - -1 -1 - - 2 - 2 - -
and by step a[5] we have the following
c 0 1 2 3 4 5 6 7 8 9
0 - -1 -1 - - 2 - 5 - 7
这样，当我们到达 a[4] 处的第 2 个 7 时，我们知道 2 是迄今为止的最大值，我们需要做的就是循环返回 a[i-1] 直到我们再次遇到比较 a[ 的 7 i] 的值改为 c[7] 中的值，如果更大，则替换 c[7]。一旦 a[i-1] = 7，我们将 c[7] 放入 b[i] 并继续下一个 a[i]。
我可以看到这种方法的主要缺点是：