有关基数排序的Java实现的解释

我在阅读并学习基数排序的Java实现，如下所示。如果有人能够澄清pointTo，index和globalPtr的逻辑含义，那将会很棒。有关基数排序的Java实现的解释

https://www.hackerrank.com/challenges/string-similarity/editorial

private void radixSort0() { 
    globalPtr = 0; 
    Arrays.fill(bucketHead, -1); 
    Arrays.fill(next, -1); 

    for (int i = 0; i < n; i++) { 
     int value = nr0[index[i]]; 
     if (bucketHead[value] == -1) bucketHead[value] = bucketTail[value] = globalPtr; 
     else bucketTail[value] = next[bucketTail[value]] = globalPtr; 
     pointTo[globalPtr++] = index[i]; 
    } 

    int ptr = 0; 
    for (int i = 0; i < M; i++) 
     for (int j = bucketHead[i]; j != -1; j = next[j]) 
      index[ptr++] = pointTo[j]; 
}

来源

2016-02-20 Lin Ma

donot发布hackerrank问题的答案更好地尝试一些东西，并张贴您的代码进行一些修改。快乐编码 – SmashCode

永远不要模仿这种风格来命名，（不）评论，代码，程序。简单的部分是'globalPtr'：allocate_的_next索引。与hackerrank的链接需要登录 - 内容是否与[lydxlx's]（https://github.com/zeyuanxy/hacker-rank/blob/master/algorithms/strings/string-similarity/Solution.Java）相同？ – greybeard

谢谢@greybeard，那么pointTo的逻辑意义是什么？ –

这radixSort0()不是完整的基数排序。如果您的目标是了解基数排序，请查看其他地方。
在两个（不必要的重复）radixSort方法中，int[] next用于建立单链表 - 使用索引而不是引用，-1和-1而不是null。（您可以而不是只需设置next[some_index_depending_on value]到index[i] - 将不会有列表。）int[] pointTo可能会更具描述性地命名为value。将next&value想象为链接列表，用包含两个数组成员的实例表示，作为具有成员next&value的实例数组的替代方案。 globalPtr是尚未在那个/那些数组中分配的最小索引。

（代码中没有注释的原因是由于我不理解为什么任何人应该尝试使用它来构造后缀数组，或者代码段对此目标有何贡献：请随时纠正&修改。）
甚至没有思考的测试，处理这个Java的方式可能是

private void radixSortStep(int[]nr) { 
    List<Integer> value[] = new List[M]; 
    for (int i = 0; i < value.length; i++) 
     value[i] = new ArrayList<Integer>(0); 

    for (int i: indexes) 
     value[nr[i]].add(i); 

    int ptr = 0; 
    for (int i = 0; i < M; i++) 
     for (int val: value[i]) 
      indexes[ptr++] = val; 
}

（有位挥手约M（设置为N + 1）和nr1（初始化项不可复制从排名到n，而不是-1））

来源

2016-02-22 14:51:54 greybeard

谢谢greybeard，致力于学习你的代码。对github版本的代码有更多的疑惑，我回顾了github链接中的代码，如果您能评论我们为什么不能只使用'bucketTail [value] = next [bucketTail [value]] = index [i ]'，并完全删除'pointTo'和'globalPrt'的用法。我认为我们可以安全地使用index [i]，而不是使用pointTo/globalPtr来获得另一个间接级别。如果我错了，请随时纠正我。谢谢。 –

我在括号里试过：'next []'和'bucketTail []'是'List'基础结构，只有'pointTo []'包含（index-）值。 – greybeard

嗨greybeard，爱你优雅的执行！同意你的所有评论，除了这个，“你不能只设置'next [some_index_depending_on的值]'index'我将不会有列表。”，假设我们正在为21和31进行基数排序，目前在一个。 21将作为头部和尾部插入到桶中，我们将直接在bucketHead [1]和bucketTail [1]中指定其位置（此例中为0），当我们处理31时（其位置为1，这是值指数的[1]），我们应该能够将其分配到下一bucketTail， –

import java.io.*; 
import java.util.*; 

public class St { 
    public static int calculate(String s){ 
     char[]arr=s.toCharArray(); 
     int length=arr.length; 
     int count=length; 
     for(int i=1;i<length;i++){ 
      int len=length-i; 
      int j=0; 
      for(;j<len;j++) 
       if(arr[j]!=arr[j+i]){ 
        break; 
       } 
      count+=j; 
     } 
     return count; 
    } 
    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     int n=scanner.nextInt(); 
     for(int i=0;i<n;i++){ 
      String s=scanner.next(); 
      System.out.println(calculate(s)); 
     } 
    } 
}

几乎过去了，除了最后两个测试用例都因超时希望我的工作可以帮助编码快乐..

来源

2016-02-20 03:40:15 SmashCode

感谢SmashCode，你的回复与我的问题有关吗？ :) –

如果你的意思是我如何告诉测试用例的数量通过我也是hackerrank用户，那么将会有添加评论按钮。 – SmashCode

谢谢SmashCode，我认为你的代码比SuffixArray运行速度慢？你的代码运行O（n^2）？ –

有关基数排序的Java实现的解释

回答

相关问题