LeetCode.937-重新排序日志數組(Reorder Log Files)

這是悅樂書的第358次更新，第385篇原創

01 看題和準備

今天介紹的是

LeetCode

算法題中

Easy

級别的第

220

題（順位題号是

937

）。你有一系列日志。每個日志都是以空格分隔的單詞串。

每個日志中的第一個單詞是辨別符，由字母數字組成。

字母日志，辨別符後面的每個單詞隻包含小寫字母。

數字日志，辨別符後面的每個單詞隻包含數字。

每個日志在其辨別符後至少有一個單詞。

重新排序日志，以便所有字母日志都在任何數字日志之前。字母日志按字典順序排序，忽略辨別符，在特定的情況下使用辨別符。數字日志應按其原始順序排列。傳回日志數組的最終順序。例如：

輸入：["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"]

輸出：["g1 act car", "a8 act zoo", "ab1 off key dog", "a1 9 2 3 1", "zo4 4 7"]

輸入：["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 act car", "a8 act car"]

輸出：["a8 act car", "ab1 act car", "g1 act car", "a1 9 2 3 1", "zo4 4 7"]

注意：

• 0 <= logs.length <= 100
• 3 <= logs [i] .length <= 100
• logs[i]保證有辨別符，辨別符後面有一個單詞。

02 第一種解法

題目的意思是給一個字元串數組，每個字元串可以分為字母字元串、數字字元串，按照下面的規則排序：

• 所有字母字元串排在前，數字字元串排在後。
• 如果是數字字元串，依舊還按照原來的順序排。

而字母字元串的排序規則如下：

• 字母字元串除去标志位後，按剩下的字元串的字典順序排序，即小的字母在前，大的字母在後。
• 如果所有字元串除去标志位後，他們剩下的字元串全都相等，那麼就需要按照标志位來排序，标志位也按照字典順序來排，依舊是小的字母在前，大的字母在後。

我們可以先将數組中所有的元素區分出來，分别存入兩個

List

中，再對其中隻存字母日志的

List

進行排序，而根據上面這些排序規則，我們可以重寫

compare

方法，通過實作

Comparator

接口來完成，因為我們使用了List，是以我們排序方法需要使用

Collections

的

sort

方法。

public String[] reorderLogFiles(String[] logs) {
    List<String> list = new ArrayList<String>();
    List<String> list2 = new ArrayList<String>();
    for (String log : logs) {
        String[] tem = log.split(" ");
        if (Character.isLetter(tem[1].charAt(0))) {
            list.add(log);
        } else {
            list2.add(log);
        }
    }
    // 排序
    Comparator<String> com = new Comparator<String>() {

        @Override
        public int compare(String o1, String o2) {
            int index = o1.indexOf(' ');
            int index2 = o2.indexOf(' ');
            // 标志位
            String flag = o1.substring(0, index);
            String flag2 = o2.substring(0, index2);
            // 标志位後面的字元串
            String left = o1.substring(index+1);
            String left2 = o2.substring(index2+1);
            // 先比較标志位後面的字元串
            int tem = left.compareTo(left2);
            // 如果标志位後面的字元串都相等，就比較标志位
            return tem == 0 ? flag.compareTo(flag2) : tem ;
        }

    };
    Collections.sort(list, com);
    list.addAll(list2);
    return list.toArray(new String[list.size()]);
}
           

03 第二種解法

對于第一種解法，我們也可以直接實作

Comparator

接口，重寫

compare

方法，思路都是一樣的。

public String[] reorderLogFiles2(String[] logs) {
    Comparator<String> com = new Comparator<String>() {
        @Override
        public int compare(String s, String s2) {
            String[] arr = s.split(" ");
            String[] arr2 = s2.split(" ");
            boolean isDigit = Character.isDigit(arr[1].charAt(0));
            boolean isDigit2 = Character.isDigit(arr2[1].charAt(0));
            // 都是字母
            if (!isDigit && !isDigit2) {
                int tem = s.substring(s.indexOf(' ')+1).compareTo(s2.substring(s2.indexOf(' ')+1));
                if (tem == 0) {
                    return arr[0].compareTo(arr2[0]);
                }
                return tem;
            }
            return isDigit ? (isDigit2 ? 0 : 1) : -1;
        }
    };
    Arrays.sort(logs, com);
    return logs;
}
           

04 小結

算法專題目前已連續日更超過七個月，算法題文章226+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！