java - 查找单词的规范形式(与 mergeSort、java 相关)

Question

我一直致力于制作一个单词的规范形式(一个单词的规范形式包含与原始单词相同的字母，但按排序顺序排列。例如，“computer”的规范形式是“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 ++;
        }
    }
}
}

Answer 1

缺陷是，如果 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. 两个部分都有可用的符号。选取值(value)最小的一项。
2. 符号仅在左侧可用。复制它们。
3. 符号仅在右侧部分可用。复制它们。