Facebook interview - Suffix Array Order - 我的博客 - ITeye技术网站

Facebook interview - Suffix Array Order - 我的博客 - ITeye技术网站

首先定义了suffix string 或者说suffix arrary
如果有个数组是 int[] text = {10, 20, 30, 25}
那么 suffix[0] = {10, 20, 30, 25}
           suffix[1] = {20, 30, 25}
           suffix[2] = {30, 25}
           suffix[3] = {25}
如果对这些数组进行lexical order 的排序，我们可以得到
suffix[0] < suffix[1] < suffix[3] < suffix[2]
问题是：
    input: int[] text
    output: int[] suffix_array_order
e.g.
input: int[] text = {10, 20, 30, 25}
output: int[] suffix_array_order = {0, 1, 3, 2}

 

Solution:

注意： Arrays.sort(T[], Comparator)只能用于排序对象数组，不能用于排序int, long之类的原始值数组！

Read full article from Facebook interview - Suffix Array Order - 我的博客 - ITeye技术网站