0

我坚持制作单词的规范形式（单词的规范形式包含与原始单词相同的字母，但按排序顺序。例如，“计算机”的规范形式是“cemoprtu”（考虑它们的字母顺序）， “程序”的那个是“agmoprr”。）

我使用 mergeSort 对单词的字母进行排序，使用以下代码。然而，它只是给了我原始词而不是规范形式。谁能告诉我我的代码有什么问题？

public static String canonicalForm(String word) {
    char[] string = new char[word.length()];
    for (int i = 0; i < word.length(); i ++) {
        string[i] = word.charAt(i);
    }
    mergeSort(string);
    String result = "";
    for (char ch: string) {
        result += ch;
    }
    System.out.println(result);
}

public static void mergeSort(char[] string) {
    if (string.length > 1) {
        char[] left = Arrays.copyOfRange(string, 0, string.length/2);
        char[] right = Arrays.copyOfRange(string, string.length/2, string.length);
        mergeSort(left);
        mergeSort(right);
        merge(string, left, right);
    }
}

public static void merge(char[] string, char[] left, char[] right) {
    int i1 = 0;
    int i2 = 0;
    for (int i = 0; i < string.length; i ++) {
        if (i1 < left.length) {
            if (left[i1] - right[i2] <= 0) {
                string[i] = left[i1];
                i1 ++;
            }
        } else if (i2 >= right.length) {
            string[i] = left[i1];
            i1 ++;
        } else {
            string[i] = right[i2];
            i2 ++;
        }
    }
}
}
4

2 回答 2

3

缺陷是如果left[i1] - right[i2] > 0，您的合并不会从右侧复制符号。

这有效：

public static void merge(char[] string, char[] left, char[] right) {
    int i1 = 0;
    int i2 = 0;
    for (int i = 0; i < string.length; i++) {
        if (i1 < left.length && i2 < right.length) {
            if (left[i1] - right[i2] <= 0) {
                string[i] = left[i1];
                i1++;
            } else {
                string[i] = right[i2];
                i2++;
            }
        } else if (i2 >= right.length) {
            string[i] = left[i1];
            i1++;
        } else {
            string[i] = right[i2];
            i2++;
        }
    }
}

你有三种情况：

  1. 两个部分都有可用的符号。取一个价值最小的。
  2. 符号仅在左侧可用。复制它们。
  3. 仅在右侧部分有可用的符号。复制它们。
于 2014-04-15T09:09:35.157 回答
2

我不确定你为什么要重新发明轮子，但这可以在没有自定义实现排序、字符串连接等的情况下编写。

public static String canonicalForm(final String word) {
    final char[] string = word.toCharArray();
    Arrays.sort(string);
    final String result = new String(string);
    System.out.println(result);
    return result;
}
于 2014-04-15T09:14:57.417 回答