LintCode 1380 Log Sorting (LeetCode 937 Reorder Log Files)

思路

• 重写比较器对日志内容为字母的日志进行排序：其中可以调用String的compareTo方法，因为其返回值符合比较器的compare函数的返回值规则。具体实现：首先利用String的indexOf找到第一个空格的位置，然后就可以把原日志分成id与内容两个字符串。然后就可以按照规则进行比较了。
• 主函数的实现：用一个list存字母型日志，方便后面直接调用sort方法排序。倒着遍历所有日志，遇到数字型日志就放到结果数组res的最后（因为正向遍历的话就无法提前知道一共有多少个字母型日志，所以数字型日志的存放位置就无法得到）。最后将排序后的字母型日志依次放到结果数组res里即可。

代码

此处为LintCode 1380的代码，与LeetCode 937可能稍有不同

public class Solution {
    /*** @param logs: the logs* @return: the log after sorting*/class MyComparator implements Comparator<String> {
    // for the log with a content of letterpublic int compare(String s1, String s2) {
    // index of the 1st space int space_s1 = s1.indexOf(' ');int space_s2 = s2.indexOf(' ');// idString id_s1 = s1.substring(0, space_s1);String id_s2 = s2.substring(0, space_s2);// contentString cont_s1 = s1.substring(space_s1 + 1);String cont_s2 = s2.substring(space_s2 + 1);if(cont_s1.equals(cont_s2)) {
    return id_s1.compareTo(id_s2);} else {
    return cont_s1.compareTo(cont_s2);}}}public String[] logSort(String[] logs) {
    // Write your code hereList<String> log_letter = new ArrayList<>();String[] res = new String[logs.length];int index = logs.length - 1;for(int i = logs.length - 1; i >= 0; i--) {
    String s = logs[i];int space = s.indexOf(' ');String cont = s.substring(space + 1);// content may start with a blankchar c = cont.trim().charAt(0);if('0' <= c && c <= '9') {
    res[index--] = s; } else {
    log_letter.add(s);}}Collections.sort(log_letter, new MyComparator());index = 0;for(String s : log_letter) {
    res[index++] = s;}return res;}
}

复杂度

时间复杂度$O(n?k+m?log(m))$: n为所有日志条数，m为字母型日志条数， k为日志平均长度(id+content)
空间复杂度$O(n?k)$