有關基數排序的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實現的解釋

回答

相關問題