说来惭愧，已经四个月没有切 leetcode 上的题目了。
虽然工作中很少（几乎）没有用到什么高级算法，数据结构，但是我一直坚信 "任何语言都会过时，只有数据结构和算法才能永恒"。leetcode 上的题目，截止目前切了 137 道（all solutions），只写过 6 篇题解，所以我会写题解的一般都是自认为还蛮有意思或者蛮典型的题目，就比如这道题。
题目链接：Count of Smaller Numbers After Self
这道题很有意思，给出一个数组，返回一个新的数组，新数组每个元素表示原数组中对应位置右边比该元素小的元素个数。听不懂了吧？举个栗子：
数组 nums = [5, 2, 6, 1]
5 右边有 2 个元素比 5 小（2 和 1）
2 右边有 1 个元素比 2 小 （1）
6 右边有 1 个元素比 6 小（1）
1 右边有 0 个元素比 1 小
所以返回数组 [2, 1, 1, 0]
leetcode 有一点不大好，就是不给数据大小范围，所以我相信绝大多数人会和我一样，先写个两层循环的 O(n^2) 代码，一提交，超时了，它给出超时数据，数组长度 20000+，O(n^2) 复杂度都好几亿了！
来分析下这道题，需要求右边比该数小的数的个数，所以有一点很明确，我们需要从右往左遍历数组。还是以上面的数组举例，也就是说当我们遍历到 index=0 时，需要知道现在已经有 1， 2， 6 三个数据了，我们需要一种数据结构，能保存 1， 2， 6， 同时之后能把 5 插进去。
首先映入脑海的是树状数组（直接把此题搞复杂了）。（不了解树状数组的可以参考我之前的文章 【前端也要学点数据结构】 神奇的树状数组 以及 【前端也要学点数据结构】神奇的树状数组的三大应用）
和改点求段很像，求右边比之小的数量，是为 "求段"，求完后把该点插进入，是为 "改点"。但是我们还需要改变传统树状数组求解的思路，把数组元素大小当做下标，而不是元素的索引位置，比如说 A[1] 其实是表示 1 的数量，而 C[2] 其实是表示 1 和 2 的数量和，所以 "改点" 的时候增量都是 1，有种 "大材小用" 之感。更蛋疼的是，由于不知道数据大小，还需要进行离散化。
目标是将 [5, 2, 6, 1] 转换成 [3, 2, 4, 1] 这样，然后再用树状数组求解。
离散化，需要先排序，再离散，最后再排回来：
var arr = []
, len = nums.length;
// array to object
// 增加 index 属性，以便离散化
for (var i = 0; i < len; i++) {
var tmp = {};
tmp.index = i;
tmp.value = nums[i];
arr.push(tmp);
}
arr.sort(function(a, b) {
return a.value - b.value;
});
// 离散化
var maxn = 1;
for (var i = 0; i < len; i++) {
if (!i) {
arr[i].nValue = maxn;
} else {
arr[i].nValue = arr[i].value === arr[i - 1].value ? maxn : ++maxn;
}
}
arr.sort(function(a, b) {
return a.index - b.index;
});
树状数组求解：
// 树状数组
var ans = []
, sum = [];
for (var i = 0; i <= maxn; i++)
sum[i] = 0;
function lowbit(x) { return x & (-x); }
function update(index, val) {
for (var i = index; i <= maxn; i += lowbit(i))
sum[i] += val;
}
function getSum(index) {
var ans = 0;
for (var i = index; i; i -= lowbit(i))
ans += sum[i];
return ans;
}
for (var i = len - 1; i >= 0; i--) {
var nValue = arr[i].nValue;
ans.unshift(getSum(nValue - 1));
update(nValue, 1);
}
树状数组部分就是简单的更新和查询了。完整代码可以参考 树状数组解法。
虽然 Accept 了，但是耗时 300ms+，仅击败了 35% 的 Javascript solutions，一看最佳答案在 200ms 左右，开始怀疑是不是有 O(n) 的解法，但是思忖良久也没有想到，想想是不是 4 次的 nlogn 耗时巨大（离散两次 sort，树状数组查询和更新各一次）。
还是拿 [5, 2, 6, 1] 举例，当枚举到 5 时，要求 [1, 2, 6] 中小于 5 的数量，同时之后又可以把 5 插进入，维护一个二叉检索树（BST）似乎是可行的？不不不，这不是赤裸裸的二分查找吗！！！
二分查找 [1, 2, 6] 中小于 5 的个数，查完之后把 5 塞进数组，维护数组的单调性，而且 Javascript 正好有 splice() 方法可以把一个数字插入数组。
二分部分返回小于 target 的数量，同时也是插入 target 的位置（index）：
// binary search
function bSearch(target, a) {
var start = 0
, end = a.length - 1;
while(start <= end) {
var mid = ~~((start + end) >> 1);
if (a[mid] >= target)
end = mid - 1;
else if (a[mid] < target)
start = mid + 1;
}
return start;
}
完整代码可以参考 二分查找解法
但是遗憾的是，尽管从 4 次 nlogn 下降到了 1 次 nlongn，但是耗时不降反升了，究其原因，我觉得是 unshift() 方法和 splice() 方法的大量调用，你觉得呢？
个人暂时没有想出 O(n) 的线性解法（可能就是没有），但是实实在在有 200ms 的 Javascript solution，难道是 BST 么？欢迎有想法的同学跟我交流探讨。