g***j
发帖数: 1275 | 1 给定给定字母 a－z，但是相互顺序不是原始的顺序，然后给定一个排序的word的序列
，通过这个序列重建字母表的相互顺序。 |
j******i
发帖数: 244 | 2 根据新的lexicographic order对字母做拓扑排序。 |
g***j
发帖数: 1275 | 3 你可能把意思理解错了，是给定了排好序的dictionary，然后求lexicographic order
【在 j******i 的大作中提到】
: 根据新的lexicographic order对字母做拓扑排序。
|
p*****2
发帖数: 21240 | 4
order
还是toposort把？
【在 g***j 的大作中提到】
: 你可能把意思理解错了，是给定了排好序的dictionary，然后求lexicographic order
|
k*********6
发帖数: 738 | 5 借下宝地哈。二爷帮俺贴个median of two sorted array的解法吧。俺自己写的丑的不
能看的说。。。我前面发帖末人回。。。
【在 p*****2 的大作中提到】
:
: order
: 还是toposort把？
|
p*****2
发帖数: 21240 | 6
好像有人给你回了，不过是C++的，Java的稍微麻烦点，但是意思差不多。
【在 k*********6 的大作中提到】
: 借下宝地哈。二爷帮俺贴个median of two sorted array的解法吧。俺自己写的丑的不
: 能看的说。。。我前面发帖末人回。。。
|
j******i
发帖数: 244 | 7 lexicographic order的意思就是字典里排词的order。如果字母表只有三个字母abc，
正常字典的lexicographic order是：
aaa
aab
aac
aba
...
ccb
ccc
如果一个不懂拉丁字母表的人，如何知道abc三个的排序呢？建一个图将abc三个字母分
别做顶点，x->y表示x在y前面。从aaa在aab前面可知a->b，从aab在aac前面可以得知b-
>c，然后就搞定了a->b->c这个关系。
当全部26个字母都用上，字典包括所有词汇的时候，你可以想象你可以建立以这26个字
母为顶点的巨大的有向图，然后做一个拓扑排序，就得到的a->b->c...->z
当26个字母的顺序被打乱了以后，可以对打乱后的字典如法炮制，得到新的拓扑序列，
比如
q->s->m->...->p
和正常的字母序列一比较，就知道对应关系了
a=>q
b=>s
c=>m
...
z=>p
order
【在 g***j 的大作中提到】
: 你可能把意思理解错了，是给定了排好序的dictionary，然后求lexicographic order
|
s*****n
发帖数: 994 | 8 只要把每个word和其上一个比较就足够了吧？（从msb比到lsb）
【在 j******i 的大作中提到】
: lexicographic order的意思就是字典里排词的order。如果字母表只有三个字母abc，
: 正常字典的lexicographic order是：
: aaa
: aab
: aac
: aba
: ...
: ccb
: ccc
: 如果一个不懂拉丁字母表的人，如何知道abc三个的排序呢？建一个图将abc三个字母分
|
|
j******i
发帖数: 244 | 9 实际的字典不可能是所有permutation都包括的。比如apple后面不是applf。
【在 s*****n 的大作中提到】
: 只要把每个word和其上一个比较就足够了吧？（从msb比到lsb）
|
s*****n
发帖数: 994 | 10 是，我的意思是只和上一个词比较，循环整个辞典一次，找到的dag和每个word互相比
较（n^2）的dag应该是一样的吧？
我感觉是这样，但是不知道怎么证明
【在 j******i 的大作中提到】
: 实际的字典不可能是所有permutation都包括的。比如apple后面不是applf。
|
j******i
发帖数: 244 | 11 对的，想象你有三个词，A、B和C和三个字母xyz，通过AB比较的出x->y，通过BC比较得
出y->z。得到的DAG是x->y->z。在拓扑排序时我们要求一个节点必须出现在所有通过它
可以达到的节点之前，因此比较AC得出x->z已经是多余信息了。
【在 s*****n 的大作中提到】
: 是，我的意思是只和上一个词比较，循环整个辞典一次，找到的dag和每个word互相比
: 较（n^2）的dag应该是一样的吧？
: 我感觉是这样，但是不知道怎么证明
|
g***j
发帖数: 1275 | 12 请问，如何通过AB比较的出x->y，只能比较第一个字母吧？如果第一个不一样，后面的
就不能比较了
【在 j******i 的大作中提到】
: 对的，想象你有三个词，A、B和C和三个字母xyz，通过AB比较的出x->y，通过BC比较得
: 出y->z。得到的DAG是x->y->z。在拓扑排序时我们要求一个节点必须出现在所有通过它
: 可以达到的节点之前，因此比较AC得出x->z已经是多余信息了。
|
