给定一个正整数数组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 5 7b[0] = -1因为没有小于2的数字b[1] = -1因为没有小于1的数字{2}，从b[2] = 2小于7的最接近7的数字是2{2,1}，从b[3] = 2小于5的最接近5的数字是2{2,1,7}，从b[4] = 5小于7的最接近7的数字是5
我正在考虑实现平衡二叉树，但是它需要很多工作。有更简单的方法吗？
最佳答案
这里有一个（近似）O（n logn）算法的草图，它介于实现插入排序和平衡二叉树的困难之间：向后做这个问题，使用merge/quick排序，使用二叉搜索。
伪码：
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.长度此方法插入排序方法
100 0.0262毫秒0.0204毫秒
1000 0.2300毫秒0.8793毫秒
10000 2.7303毫秒75.7155毫秒
100000 32.6601毫秒7740.36毫秒
300000 98.9956ms 69523.6毫秒
1000000 333.501毫秒？？？？？不够耐心
所以，正如您所看到的，这个算法比我之前发布的插入排序方法增长得慢得多。然而，插入排序方法需要73行代码，而不是26行代码因此，就简单性而言，如果您没有时间要求/输入很小，插入排序方法可能仍然是一种方法。