每日一题做题记录,参考官方和三叶的题解

目录
  • 题目要求
  • 思路:花样应用排序+自定义类优化
    • Java
      • Collections.sort()
    • C++
      • STL stable_sort()
  • 总结

题目要求

思路:花样应用排序+自定义类优化
  • 根据题意重写语言自带的排序方法进行排序;
  • 由于排序中每个元素会被访问到很多次,防止每次都临时判断它属于什么类别巴拉巴拉,自定义一个Log类用来存放预处理结果。
    • Log类包括:
      • t y p e type type:类型, 1 1 1为数字日志, 0 0 0为字母日志;(其实根据排序规则,只要保证 数 字 > 字 母 数字>字母 数字>字母就可以)
      • i n d e x index index:原来所在的位置,用于维持数字日志顺序,若为稳定排序则无需该项;
      • o r i ori ori:原文内容,用于构造结果;
      • i d e n t i f i e r identifier identifier:标识符;
      • c o n t e n t content content:除标识符外的正文内容。
    • 构造函数时输入日志原文和在数组内的下标。
Java
class Solution {
    class Log {
        int type, index;
        String ori, identifier, content;
        Log(String s, int idx) {
            index = idx;
            int n = s.length(), i = 0;
            while(i < n && s.charAt(i) != ' ') // 找第一个空格
                i++;
            identifier = s.substring(0, i);
            content = s.substring(i + 1);
            ori = s; // 原日志内容,用于构成结果
            type = Character.isDigit(content.charAt(0)) ? 1 : 0; // 数字为1,字母为0(保证数字>字母)
        }
    }

    public String[] reorderLogFiles(String[] logs) {
        int n = logs.length;
        List List = new ArrayList<>();
        for(int i = 0; i < n; i++)
            List.add(new Log(logs[i], i));
        Collections.sort(List, (a, b) -> {
            if(a.type != b.type) // 数字在字母后(1在0后)
                return a.type - b.type;
            if(a.type == 1) // 都是数字:按原序
                return a.index - b.index;
            // 都是字母:内容相同按标识,不同按内容
            return a.content.equals(b.content) ? a.identifier.compareTo(b.identifier) : a.content.compareTo(b.content);
        });

        String[] res = new String[n];
        for(int i = 0; i < n; i++)
            res[i] = List.get(i).ori;
        return res;
    }
}
  • 时间复杂度: O ( n log ⁡ n ) O(nlog n) O(nlogn),初始化复杂度为 O ( n ) O(n) O(n),即遍历一遍输入日志;排序复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn);构造答案复杂度为 O ( n ) O(n) O(n),也是遍历一次。
  • 空间复杂度: O ( n ) O(n) O(n),存放初始化结果和答案。
Collections.sort()
  • 学习参考链接
  • 一个排序方法没什么好说的,主要是里面的comparator的重写;
  • 不稳定排序,所以上面用原数组下标的比较来确定前后关系;
  • return a-b( 前 面 − 后 面 前面-后面 前面−后面)表示升序排列,反之为降序排列;
  • compareTo()方法默认是将二者升序排列。
C++
class Solution {
public:
    class Log {
    public:
        int type;
        string ori, identifier, content;
        Log(string s) {
            ori = s;
            int n = s.size(), i = 0;
            while(i < n && s[i] != ' ') // 找第一个空格
                i++;
            identifier = s.substr(0, i);
            content = s.substr(i + 1, n - 1 - i);
            type = isdigit(content[0]) ? 1 : 0; // 数字为1,字母为0
        }
    };
    
    vector reorderLogFiles(vector& logs) {
        int n = logs.size();
        vector List;
        for(int i = 0; i < n; i++)
            List.push_back(new Log(logs[i]));
        stable_sort(List.begin(), List.end(), [](Log* a, Log* b) {
            if(a->type != b->type) // 数字在字母后(1在0后)
                return a->type < b->type;
            if(a->type == 1) // 都是数字:按原序
                return false;
            // 都是字母:内容相同按标识,不同按内容
            return (a->content == b->content) ? (a->identifier < b->identifier) : (a->content < b->content);
        });
            

        vector res(n);
        for(int i = 0; i < n; i++)
            res[i] = List[i]->ori;
        return res;
    }
};
  • 时间复杂度: O ( n log ⁡ n ) O(nlog n) O(nlogn),初始化复杂度为 O ( n ) O(n) O(n),即遍历一遍输入日志;排序复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn);构造答案复杂度为 O ( n ) O(n) O(n),也是遍历一次。
  • 空间复杂度: O ( n ) O(n) O(n),存放初始化结果和答案。
STL stable_sort()
  • 学习参考链接
  • 顾名思义,STL库内置的一个稳定排序方法(两个相同值排序后相对位置不变)。
  • return false表示不改变二者顺序;
  • return a < b( 前 面 < 后 面 前面<后面 前面<后面)表示升序排列。
总结

是一道少见的思路简单实现难的题目,理解了半天Java和C++的sort方法(之前几次用都比较简单),然后C++调了半天定义类以及调用时候的*,其实还是没太理解哪里需要加,放着下次一定……

【要开始无敌忙碌的一个月了】

欢迎指正与讨论!

1.《Java&C++题解与拓展——leetcode937.重新排列日志文件【Collections.sort()、stable》援引自互联网,旨在传递更多网络信息知识,仅代表作者本人观点,与本网站无关,侵删请联系页脚下方联系方式。

2.《Java&C++题解与拓展——leetcode937.重新排列日志文件【Collections.sort()、stable》仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证。

3.文章转载时请保留本站内容来源地址,https://www.lu-xu.com/jiaoyu/2372278.html