Java 中的循环后缀数组使用比较器

Question

我正在尝试在 Java（Suffix array 维基百科）中实现 CircularSuffixArray class。在我的方法中，我创建了一个实现 Comparator 的内部 class 来比较每个后缀的第一个字符，如果它们相等，则递归调用 compare 下一个字符。像这样：

public class CircularSuffixArray {
    private String string;
    private int[]  sortSuffixes;

    private class SuffixesOrder implements Comparator<Integer> {
        public int compare(Integer i, Integer j) {
            if      ((length() - 1) < i) return 1;
            else if ((length() - 1) < j) return -1;
            if (string.charAt(i) != string.charAt(j))
                return compare(string.charAt(i), string.charAt(j));
            else
                return compare(i+1, j+1);
        }

        private int compare(char a, char b) {
            return b - a;
        }
    }   

    private Comparator<Integer> suffixesOrder() {
        return new SuffixesOrder();
    }

    // circular suffix array of s
    public CircularSuffixArray(String s) {
        if (s == null) throw new NullPointerException("null argument");
        string = s;
        sortSuffixes = new int[length()];
        for (int i = 0; i < length(); i++)
            sortSuffixes[i] = (length() - 1) - i;
        Arrays.sort(sortSuffixes, suffixesOrder());
    }
}

但是当我试图编译它时，我得到了这个错误：

CircularSuffixArray.java:35: error: no suitable method found for sort(int[],Comparator<Integer>) Arrays.sort(sortSuffixes, suffixesOrder());

打电话告诉我：

首先，如果实现没问题（我现在有很多代码相关但我想自己尝试）
尽管 "algorithm" 是错误的，你能帮我弄清楚为什么会出现这个错误吗？

Answer 1

就我所见，我认为你的做法是可以的。我相信，您收到错误的原因是您混合了 int 和 Integer。 Java 会自动进行一些拆箱（即将整数转换为整数）和装箱（将整数转换为整数），但在数组的情况下不会。

如果您查看数组 class (https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html)，您将找到您尝试调用的排序方法：

sort(T[] a, Comparator<? super T> c)

T[] 表示您的数组必须是可扩展类型，而原语不是。所以你需要让你的数组类型为 Integer[] 而不是 int[].

我也不知道length()是在哪里定义的。我假设你想要字符串的长度，所以我会添加以下方法：

public int length() {
    return string.length();
}

Java 中的循环后缀数组使用比较器

Circular Suffix Array in Java using Comparator

java

sorting

algorithm

suffix