题解 | #查找兄弟单词#

import java.util.*;
public class Main {
    // 自定义一个比较器，实现将所有的兄弟单词按照字典序进行排列
    public static class ComparaString implements Comparator<String> {
        @Override
        public int compare(String str1, String str2) {
            int len1 = str1.length();
            int len2 = str2.length();
            int p1 = 0;
            int p2 = 0;
            while (p1 < len1 && p2 < len2) {
                if (str1.charAt(p1) < str2.charAt(p2)) {
                    return -1;
                } else if (str1.charAt(p1) > str2.charAt(p2)) {
                    return 1;
                } else {
                    p1++;
                    p2++;
                }
            }
            if (len1 < len2) {
                return -1;
            } else if (len1 > len2) {
                return 1;
            } else {
                return 0;
            }
        }
    }
    // 整个程序的入口函数
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String originalStr = scan.nextLine();
        String[] strs = originalStr.split(" ");
        int n = Integer.valueOf(strs[0]); // n -> 字典中单词的个数
        int k = Integer.valueOf(strs[strs.length - 1]); // k -> 按字典序排列后的第 k 个单词是什么
        String x = strs[strs.length - 2]; // 需要查找的单词
        ArrayList<String> brothers = new ArrayList<>(); // 定义一个一维数组，用于存放 x 的兄弟单词
        for (int i = 0; i < n; i++) {
            if (isBrother(strs[i + 1], x)) { // 如果是兄弟单词
                brothers.add(strs[i + 1]);
            }
        }
        System.out.println(brothers.size());
        if (brothers.size() < k) {
            return;
        }
        brothers.sort(new ComparaString());
        System.out.println(brothers.get(k - 1));
//         String[] strBrothers = new String[brothers.size()];
//         for (int i = 0; i < brothers.size(); i++) {
//             strBrothers[i] = brothers.get(i);
//         }
//         System.out.println(heapSort(strBrothers, k));
    }
    // 自定义一个函数，用来判断两个字符串是否是兄弟单词
    public static boolean isBrother(String str1, String str2) {
        if (str1.equals(str2)) {
            return false;
        }
        int len1 = str1.length();
        int len2 = str2.length();
        if (len1 != len2) {
            return false;
        }
        str1 = process(str1);
        str2 = process(str2);
        return str1.equals(str2);
    }
    // 自定义一个函数，实现将传进来的字符串中的字符按照字典序进行排序
    public static String process(String str) {
        char[] chrs = str.toCharArray();
        quickSort(chrs);
        StringBuffer sb = new StringBuffer("");
        for (char chr : chrs) {
            sb.append(chr);
        }
        return new String(sb);
    }
    // 自定义一个函数，实现快速排序
    public static void quickSort(char[] chrs) {
        if (null == chrs || chrs.length < 2) {
            return;
        }
        sort(chrs, 0, chrs.length - 1);
    }
    // 快速排序的主函数
    public static void sort(char[] chrs, int start, int end) {
        if (start >= end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        char tmp = chrs[end];
        while (p < r) {
            if (chrs[p] < tmp) {
                swap(chrs, p++, ++l);
            } else if (chrs[p] > tmp) {
                swap(chrs, p, --r);
            } else {
                p++;
            }
        }
        sort(chrs, start, l);
        sort(chrs, r, end);
    }
    // 自定义一个函数，实现数组中的某两个位置上的元素进行交换
    public static void swap(char[] chrs, int p1, int p2) {
        char tmp = chrs[p1];
        chrs[p1] = chrs[p2];
        chrs[p2] = tmp;
    }
    /**********************************************************************************/
    // 自定义一个函数，实现堆排序
    public static String heapSort(String[] strs, int k) {
        if (null == strs || strs.length < 2) {
            return "";
        }
        for (int i = 0; i < strs.length; i++) {
            heapInsert(strs, i);
        }
        int heapSize = strs.length;
        swap1(strs, 0, --heapSize);
        while (strs.length - heapSize != k) {
            heapify(strs, 0, heapSize);
            swap1(strs, 0, --heapSize);
        }
        return strs[k - 1];
    }
    public static void heapInsert(String[] strs, int index) {
        while (comparaString(strs[index], strs[(index - 1) / 2]) == 1) {
            swap1(strs, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    public static void heapify(String[] strs, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && comparaString(strs[left + 1], strs[left]) == 1 ? left + 1 : left;
            largest = comparaString(strs[largest], strs[index]) == 1 ? largest : index;
            if (index == largest) {
                break;
            }
            swap1(strs, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }
    public static void swap1(String[] strs, int p1, int p2) {
        String tmp = strs[p1];
        strs[p1] = strs[p2];
        strs[p2] = tmp;
    }
    public static int comparaString(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int p1 = 0;
        int p2 = 0;
        while (p1 < len1 && p2 < len2) {
            if (str1.charAt(p1) < str2.charAt(p2)) {
                return -1;
            } else if (str1.charAt(p1) > str2.charAt(p2)) {
                return 1;
            } else {
                p1++;
                p2++;
            }
        }
        if (len1 < len2) {
            return -1;
        } else if (len1 > len2) {
            return 1;
        } else {
            return 0;
        }
    }
}