G的一道题 分析

http://www.mitbbs.com/article_t/JobHunting/31903469.html

grass的解法完全正确。

[2, 0, 1, 0] 如何得到 (1, 2, 3, 4)的某个排列？
推出第一个元素一定是(1, 2, 3, 4)中排名第三的数，也就是3
然后就有点递归的意味了。
[0, 1, 0] 如何得到(1, 2, 4)的某个排列？
推出第一个元素一定是(1, 2, 4)中排名第一的数，也就是1
[1, 0]如何得到（2，4)的某个排列？
推出第一个元素一定是(2, 4)中排名第二的数，也就是4
[0]如何得到(2)的某个排列？
这个是trival case了。实际上，Count array的最后一个元素永远是0，属于无效信息。

最后推出原数组是[3, 1, 4, 2]

Let Count be the count array, let Array be the original array.
用伪代码实现如下

Create ordered set S, and add 1, 2, ..., n to S

for (i = 0; i < n; i++)
{
    int index = Count[i] + 1;
    Array[i] = S.FindKth(index);
    
    S.RemoveKth(index); 
}

/*
如果RemoveKth同时返回值，如同stack的pop操作那样，还可以简化为
for (i = 0; i < n; i++)
{
    int index = Count[i] + 1;
    Array[i] = S.RemoveKth(index);
}
*/

问题的难点在于如何实现S，使得RemoveKth操作最多是lg(n)的
如果用数组，移动操作是O(n)的
如果用链表，定位操作是O(n)的
都不符合要求

怎么办呢？实际上lg(n)本身就是一个很大的提示，你可以联想到binary search, 
quick sort, binary tree, BST, heap, 分治，递归... 一定是套用其中某个或几个的
思想。

如果考虑BST，从第i个元素这个要求，你可以想到一道经典题：
如何在log(N)时间找到BST的第i个元素？

中序遍历的方法是O(N)的，怎么办？空间换时间!(类似思路有O(1)时间取得stack的最
小值)

方法就是每个节点附加左子树的元素个数，用递归或迭代。假定BST是平衡的，这样FindKth就是log(N)的。

但是这只是FindKth是log(N), RemoveKth呢？

grass巧妙的解决了这个问题，RemoveKth和FindKth的代码几乎一样，只是多了个删除
操作。但是，无须真正删除节点！树还是那棵一开始就创建好的平衡BST, 包含了自然
数1到n。只需要标记节点被删除就可以了，同时需要更新受影响的节点的左子树元素个
数。

代码如下，index从1开始
Node remove(Node node, int index)
{
    if (node.numOfLeftChildren >= index)
    {
        // left
        node.numOfLeftChildren--;
        return remove(node.left, index);
    }
    else if (node.numOfLeftChildren + 1 == index && !node.removed)
    {
        // current
        node.removed = true;
        return node;
    }
    else
    {
        // right
        return remove(node.right, index - node.numOfLeftChildren - (node.
removed ? 0 : 1));
    }
}

也可以用迭代，因为是尾递归。
此外上述代码最好加上判断node是否null, 可以处理index越界而查找失败的情况。

自此问题得到圆满解决。

总结：
1) Try a simple example first.
2) Use pseudo code first, then focus on the details.
3) 多尝试几种不同的数据结构，比较各自的优缺点
4) 化归到经典题(数学中化归的思想, 比如一道DP题能否化归到背包问题)
5) 空间换时间的策略
6) 对树的操作一定和递归密切相关
7) 标记节点状态而不破坏原始结构的思想(比如图的遍历)
8) 其它...