LeetCode题解02_排序汇总-16题

排序算法可以说是算法的基础，很多leetcode题目也会有涉及
为了篇幅不至于太长，排序算法原理和leetcode题目分成2篇笔记进行介绍

• 1.上一篇：针对经典的十大排序算法进行介绍（点击查看）
• 2.本篇：介绍排序相关的leetcode题目解法

• 说明：csdn的markdown中原始代码注释重点不突出，因此使用carbon软件将代码转成图片了
• 附带额外截图：重新将代码中易错和重点的地方加入颜色进行标识（csdn显示有点不清晰，但是不影响学习）

下面列举了一些与排序相关的leetcode题目，为了节省篇幅，很多题目的解法只列出了核心函数；题目都是在leetcode上验证过的

part01：简单题目（3）

LC075_颜色分类

题目：整数0、1 和2分别表示红、白和蓝；原地只遍历一次排序，使相同颜色元素相邻，并按红色、白色、蓝色顺序排序

• 原始代码
  
• 有重点标识的代码
  

LC280_摆动排序（wiggle sort）

题目：重新排列成 nums[0] <= nums[1] => nums[2] <= nums[3]… 的锯齿顺序

• 原始代码
  
• 有重点标识的代码
  

LC324_摆动排序II

题目：整数数组 nums，用 O(n) 时间和O(1)空间复杂度，重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的锯齿顺序

现象：奇数位置的元素都是波峰

提示：相对于LC280，本题锯齿数数组没有等号的限制，如果数组里出现相等元素，就不能用LC280的解法

范围：小范围相等下面还可以解决，极端点所有元素都相等，题目直接得不到结果

• 原始代码
  
• 有重点标识的代码
  

part02：第K大的数（3）

LC414_第3大的数

题目：一个非空数组，返回此数组中 第三大的数 ；如果不存在，则返回数组中最大的数，时间复杂度O(n)

示例：[2, 2, 3, 1]; 输出：1；解释：一定要区分好元素和数的区别？

• 第三大的数：题目中的两个值2，只能算一个数，因此返回1

• 第三大的元素：题目中的两个值2，算两个个元素，因此返回2

• 原始代码
  

• 有重点标识的代码
  

LC215_数组中的第K个最大的元素

示例：[3,2,3,1,2,4,5,5,6] 和 k = 4；返回：4；注意，是排序后的第K个大的元素，不是K个不同的元素，即相同数不能算一个

提示：LC414可以说是本题的特例，LC414的套路可以处理本题；但当K比较大时，总不能写一堆 if… else 吧…

• 本题目想考察的实现（快排+二分）
  

• stl库函数的思路
  下面2个都用了stl的库函数，更快；本题真正考察的应该是上面不用库函数的思路
  

• 有重点标识的代码
  

LC703_数据流中的第K大的元素

实现 KthLargest 类：

• KthLargest(int k, int[] nums) - 使用整数 k 和整数流 nums 初始化对象；相当于构造函数

• int add(int val) - 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素；添加一个元素，返回第k大元素

• 原始代码
  

• 有重点标识的代码
  

part03：中位数（2）

LC295_数据流的中位数

中位数：有序列表中间的数，如果列表长度是偶数，中位数则是中间两个数的平均值

要求：设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中
• double findMedian() - 返回目前所有元素的中位数
• 原始代码
  
• 有重点标识的代码
  

LC004_寻找2个升序数组的中位数

题目：两个长度为m和m的升序的正整数数组，寻找中位数；时间复杂度为 O(log (m+n))

示例：nums1 = [1,2], nums2 = [3,4]；输出：2.5； nums1 = [], nums2 = [1]，输出 1.0

思路：在2个数组中一起找中位数，一次剔除掉 k/2 个元素，具体剔除掉哪个数组的元素看分析

• 原始代码
  
• 有重点标识的代码
  

part04：频率（3）

LC347_前K个高频元素

题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素；时间复杂度必须优于 O(n log n)

注意：返回结果中数的顺序不限制，相同元素只能算一个；map+priority_quque的小根堆实现

思路：1.统计元素出现的频率、2.对频率排序、3.找出前K个高频元素

• 1.统计元素出现的频率：直接使用map

• 2.对频率排序：使用优先级队列priority_queue

为什么不用快速排序？使用快排要将map转换为vector的结构**，然后对整个数组进行排序；本题不用全部排序，**只要维护K个有序就可以

扩展

优先级队列priority_queue：是容器适配器，缺省情况下，priority_queue利用less，优先级高的元素在前面，即队列里面是降序；间接就是一个max-heap（大根堆）完成对元素的排序，这个大根堆是以vector为表现形式的complete binary tree（完全二叉树）

大根堆（堆头是最大元素），小根堆（堆头是最小元素），用priority_queue（优先级队列）

• 3.找出前K个高频元素：使用小根堆，里面保持最多有K个元素

原理：用小根堆，因为要统计最大前k个元素，小根堆每次将最小的元素弹出，最后小跟堆里积累的才是前k个最大元素

维护k个元素的根堆的操作套路：1.先无脑的放入k个元素进入根堆；2.元素超过k个后，每次新元素依然放入，然后再弹出堆顶

• 原始代码
  
• 有重点标识的代码
  

LC451_根据字符出现频率降序排序

注意：针对一个字符串排序，相同字符要挨在一起，区分大小写；示例：“tree”，结果：“eert” or “eetr”

方法1：priority_queue实现大根堆思路

优化：因为可以自动降序，省去了方法3要逆序拼接的步骤

比较：priority_queue里放入pair时，pair的比较，先比较第一个元素，第一个相等比较第二个

细节：priority_queue先放入的是出现次数，后放入的元素

语法：在字符串的末尾添加num个字符ch，basic_string &append(size_type num，char ch);

string frequencySort(string s) {
    //1.统计频率 + 大根堆自动降序
    unordered_map<char, int> m;
    for (char c : s) ++m[c];                             //<字符，出现频率> 

    priority_queue<pair<int, char>> big_root;            //默认：大根堆（降序队列，less）
    for (auto a : m) big_root.push({a.second, a.first}); //全部放入大根堆（按频率降序）        
    //2.拼接    
    string res = "";　　　　　　　　     					//提示：不显示赋值为空字符串也不会有影响
    while (!big_root.empty()) {
        auto t = big_root.top(); big_root.pop();
        res.append(t.first, t.second);					 //(size_type num，char ch)
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法2：直接使用sort + 仿函数（运行太慢）

lambda参考：C++之Lambda表达式 - 季末的天堂 - 博客园 (cnblogs.com)

思路：sort里实现仿函数cmp，仿函数用lambda实现；如果不用lambda实现，仿函数要是static函数

lambda语法：[函数对象参数] (操作符重载函数参数) mutable 或 exception 声明 -> 返回值类型 {函数体}

string frequencySort(string s) {
    unordered_map<char, int> m;
    for (char c : s) ++m[c];
    sort(s.begin(), s.end(), [&](char& a, char& b){        //sort里实现仿函数cmp
        return m[a] > m[b] || (m[a] == m[b] && a < b);
    });
    return s;
}
1
2
3
4
5
6
7
8

方法3：不使用带排序功能的函数，用一个数组记录频率

string frequencySort(string s) {
    unordered_map<char, int> m;　　　　　　　　　　　　　　//1.统计频率（<字符，出现个数>）
    for (char c : s) ++m[c];

    vector<string> freq(s.size() + 1);                //不使用priority_queue
    for (auto &a : m) {                               //2.[出现次数] = num个字符str
        freq[a.second].append(a.second, a.first);
    }    

    string res；
    for (int i = s.size(); i > 0; --i) {              //3.逆序拼接(频率高的先开始)
        if (!freq[i].empty()) res.append(freq[i]);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LC387_字符串中第一个不同字符

题目：对字符串，找第一个不重复的字符，并返回它的索引；如果不存在，则返回 -1

示例：s = “leetcode”，返回 0；s = “loveleetcode”，返回 2

/* 思路：map统计个数，遍历找第一个次出现次数为1的元素的下标
细节：遍历的是原始数组，而不是map，这样可以保证找到第一个不同的字符 */
int firstUniqChar(string s) {
unordered_map<char, int> m;
for (char c : s) ++m[c];
for (int i = 0; i < s.size(); ++i) {	//原始数组
  if (m[s[i]] == 1) return i;
}
return -1;
}
1
2
3
4
5
6
7
8
9
10

part05：融合（5）

LC148_链表排序

题目：2个升序链表，融合，返回排序后的链表，要求时间复杂度O(nlogn)，空间复杂度是常量级

符合时间O(nlogn)有希尔，归并，快排，堆排序；用哪一个比较好？

• 快排：空间是O(logn)先排除

• 希尔排序：改进版的插入排序，由于要回退访问已经排序的内容插入，不适合链表

• 堆排序：一般用在求top上效果很好，暂时也先排除

思路：归并排序主要采用分治思想，核心是写merge函数，merge特别适合融合已经排序的内容；针对链表，当只有一个节点时，自动认为有序

实现：快慢双指针找中间断开链表，分开的2个链表递归使用merge函数

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *slow = head, *fast = head, *pre = head;    
    while (fast && fast->next) { //快慢指针找中间节点，很常用技巧，2个节点才有处理的必要
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    pre->next = NULL;            //断开链表，一定要记录slow前一个点
    return merge(sortList(head), sortList(slow));    //分治中的 分
}
ListNode* merge(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);　　　　　　　　//暂时处理了一个节点的顺序
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LC147_链表插入排序

插入排序原理：一句话，顺序遍历，遇到新元素，找到新元素在前面已排列的合适位置插入

/* 时间O(n^2)，空间O(1)，以高时间复杂度换取低空间复杂度，用一个无效节点dummy接住已排序的链表 */
ListNode* insertionSortList(ListNode* head) {
 ListNode *dummy = new ListNode(-1), *pre = dummy;
 while (head) {
     ListNode *t = head->next;

     pre = dummy;            //遍历已排序链表，每次都从头开始，低效的地方
     while (pre->next && pre->next->val <= head->val) {    
         pre = pre->next;
     }
     head->next = pre->next; //插入，前插，注意顺序
     pre->next = head;

     head = t;               //一次一个节点，低效
 }
 return dummy->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LC021_融合2个有序（升序）链表

/* 思路：新节点dummy后链接2个链表里较小节点，当一个链表处理完，将另一个链表里没有处理的链接到dummy后 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 ListNode *dummy = new ListNode(-1), *pre = dummy;
 while (l1 && l2) {
     if (l1->val < l2->val) {
         pre->next = l1; l1 = l1->next;
     } else {
         pre->next = l2; l2 = l2->next;
     }
     pre = pre->next;
 }
 pre->next = l1 ? l1 : l2;
 return dummy->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LC088_融合2个有序数组

题目：2个非递减数组num1和num2，融合结果存在num1里；

输入有点特殊：nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略；nums2 的长度为 n

/* 思路：双指针指向2个数组尾部，从后向前给num1赋值 */
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
 int i = m - 1, j = n - 1, k = m + n - 1;        //从后向前赋值num1
 while (j >= 0) {
     nums1[k--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
 }
}
1
2
3
4
5
6
7

LC023_融合k个升序链表

题目：一个链表数组，每个链表都已经按升序排列；将所有链表合并到一个升序链表中，返回合并后的链表

暴力思想：一个一个链表融合，显然会超时

/* 分治思想 + merge：2个一组进行merge，直到最后只剩下一个链表为止
   解决奇数个的链表：用 k = (n + 1) / 2，保证 k 指向后半段（有可能前半段多一个）   */
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return NULL;
    int n = lists.size();
    while (n > 1) {
        int k = (n + 1) / 2;
        for (int i = 0; i < n / 2; ++i) {
            lists[i] = mergeTwoLists(lists[i], lists[i + k]); //LC021_融合2个有序（升序）链表
        }
        n = k;
    }
    return lists[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

丑数的思路

C11，decltype和auto都可以用来推断类型，但是二者有几处明显的差异：

• 1.auto忽略顶层const，decltype保留顶层const
• 2.对引用操作，auto推断出原有类型，decltype推断出引用
• 3.对解引用操作，auto推断出原有类型，decltype推断出引用
• 4.auto推断时会实际执行，decltype不会执行，只做分析

丑数的思路：丑数本质上是维护了3个指针，指向了3个数组，每次取最小值，且只有最小值的指针会移动

• 实现：用priority_queue实现的小根堆，先将每个链表头节点放入，相当于同时维护k个指针

• 细节：lambda实现的仿函数 和 传入的地方

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode*& a, ListNode*& b) {            //lambda实现的仿函数
        return a->val > b->val;
    };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > pri_que(cmp);//小根堆，升序，greater
    for (auto node : lists) {                            //每个链表头节点放入，
        if (node) pri_que.push(node);
    }
    ListNode *dummy = new ListNode(-1), *pre = dummy;    //pre一直指向当前遍历的最小值节点
    while (!pri_que.empty()) {
        auto t = pri_que.top(); pri_que.pop();
        pre->next = t;
        pre = pre->next;
        if (pre->next) pri_que.push(pre->next);          //丑数思路
    }
    return dummy->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

参考

• 1.LeetCode All in One 题目讲解汇总(持续更新中…) - Grandyang - 博客园 (cnblogs.com)，这个博主很多解法都不错
• 2.《代码随想录》
• 3.leetcode官网，想了解详细题目，可以看官网介绍