j**l
发帖数: 2911 | 1 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) 其它... | g***o
发帖数: 4 | 2
Use skip list can get lgn too.
【在 j**l 的大作中提到】
: 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)的某个排列？
| s*****y
发帖数: 897 | 3 我想过用skip list，skip list是排好序的，search element是lgn，但是要得到排第
几的element似乎不行。
【在 g***o 的大作中提到】
:
: Use skip list can get lgn too.
| g***o
发帖数: 4 | 4 Follow the solution from gloomyturkey. Build the skip list of 1~n. Every
time, simply fetch the number at the position of count array[i] and delete
it from the list, which is lgn time.
【在 s*****y 的大作中提到】
: 我想过用skip list，skip list是排好序的，search element是lgn，但是要得到排第
: 几的element似乎不行。
| s*****y
发帖数: 897 | 5 难道我理解错了
s[i] = list.remove(a[i]); 返回这个list里面排a[i]的值，如果是delete a[i]可以
用skip list，但是现在要delete 第a[i]的值。
public int[] recover(int[] a) {
int[] s = new int[a.length];
ArrayList list = new ArrayList();
for (int i=0; i
for (int i=0; i
s[i] = list.remove(a[i]);
}
return s;
}
【在 g***o 的大作中提到】
: Follow the solution from gloomyturkey. Build the skip list of 1~n. Every
: time, simply fetch the number at the position of count array[i] and delete
: it from the list, which is lgn time.
| r******n
发帖数: 170 | 6 赞详细的解释！
【在 j**l 的大作中提到】
: 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)的某个排列？
| a*********0
发帖数: 2727 | 7 标准的order statisitc tree 是存放整棵树节点个数而不是仅仅左子树
【在 j**l 的大作中提到】
: 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)的某个排列？
|
|
