LCR074-LCR078排序

剑指offer（专项突破版）12 排序

LCR074.合并区间

分析

如果先将所有区间按照起始位置排序，那么只需要比较相邻两个区间的结束位置就能知道它们是否重叠。如果区间1的结束位置大于区间2的起始位置，说明存在重叠，取较大的结束位置。如果它们重叠就将它们合并，然后判断合并的区间是否和下一个区间重叠。重复这个过程，直到所有重叠的区间都合并为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 边界条件处理
        if(intervals.size() == 0){
            return {};
        }
        // 将数组按照起始时间排序
        sort(intervals.begin(), intervals.end());
        // 对每个区间合并
        vector<vector<int>> res{intervals[0]};  // 初始时将第一个区间放入
        for(int i = 1; i < intervals.size(); i++){
            // 当前起始时间小于前面的结束时间，说明可以合并
            if(intervals[i][0] <= res.back()[1]){
                // 修改结果中的结束时间
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
            // 否则不能合并，将该区间加入结果集
            else{
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};
ANGELSCRIPT
  • 时间复杂度：如果输入数组中有n个区间，那么将它排序的时间复杂度是O（nlogn），接着逐一扫描排序的区间数组并将相邻的区间合并。逐一扫描每个区间，时间复杂度为O(n)。总的时间复杂度为O(nlogn)。
  • 空间复杂度：最多需要O(n)存储结果。

LCR075.数组的相对排序

分析

计数排序是一种线性时间的整数排序算法。如果数组的长度为n，整数范围（数组中最大整数与最小整数的差值）为k，对于k远小于n的场景（如对某公司所有员工的年龄排序），那么计数排序的时间复杂度优于其他基于比较的排序算法（如归并排序、快速排序等）。

计数排序的基本思想是先统计数组中每个整数在数组中出现的次数，然后按照从小到大的顺序将每个整数按照它出现的次数填到数组中。

如果数组的长度为n，整数的范围为k，那么计数排序的时间复杂度就是O（n+k）。由于需要创建一个长度为O（k）的辅助数组counts，因此空间复杂度为O（k）。当k较小时，无论从时间复杂度还是空间复杂度来看计数排序都是非常高效的算法。当k很大时，计数排序可能就不如其他排序算法（如快速排序、归并排序）高效。

题目明确提出数组中的数字都在0到1000的范围内。这是一个很明显的提示，据此可以考虑采用计数排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        // 统计arr1中的次数
        int counts[1001];
        for(int i = 0; i < arr1.size(); i++){
            counts[arr1[i]]++;
        }
        // 按照arr2中的排序
        int i = 0;
        for(int num : arr2){
            while(counts[num] > 0){
                arr1[i++] = num;
                counts[num]--;
            }
        }
        // 剩余元素
        for(int k = 1; k < 1001; k++){
            while(counts[k] > 0){
                arr1[i++] = k;
                counts[k]--;
            }
        }
        return arr1;
    }
};
CPP
  • 时间复杂度：如果数组arr1的长度为m，数组arr2的长度为n，那么时间复杂度是O（m+n）。
  • 空间复杂度：由于这个题目中的数字在0到1000的范围内，上述代码用来统计每个数字出现次数的辅助数组counts的长度为1001，是一个常数，因此空间复杂度可以认为是O（1）。

LCR076.数组中的第K个最大的元素

快速排序

快速排序的基本思想是分治法，排序过程如下：在输入数组中随机选取一个元素作为中间值（pivot），然后对数组进行分区（partition），使所有比中间值小的数据移到数组的左边，所有比中间值大的数据移到数组的右边。接下来对中间值左右两侧的子数组用相同的步骤排序，直到子数组中只有一个数字为止。

如果partition返回的值为n-k，则找到了第K大元素，如果返回的索引大于n-k，则在start,index-1继续找；如果小于n-k，则在index+1,end区间继续找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int partition(vector<int>& nums, int start, int end){
        // 随机选取一个值作为pivot
        int r = rand() % (end - start + 1) + start;
        // 将其换到数组最后
        swap(nums[r], nums[end]);
        // 初始化指针
        int small = start - 1;
        for(int i = start; i < end; i++){
            if(nums[i] < nums[end]){
                small++;
                swap(nums[i], nums[small]);
            }
        }
        small++;
        swap(nums[small], nums[end]);
        return small;
    }
    int findKthLargest(vector<int>& nums, int k) {
        int start = 0;
        int end = nums.size() - 1;
        int index = partition(nums, start, end);
        int target = nums.size() - k;
        while(index != target){
            if(index > target){
                end = index - 1;
            }
            else{
                start = index + 1;
            }
            index = partition(nums, start, end);
        }
        return nums[nums.size()-k];
    }
};
CPP
  • 时间复杂度：由于函数partition随机选择中间值，因此它的返回值也具有随机性，计算这种算法的时间复杂度需要运用概率相关的知识。此处仅计算一种特定场合下的时间复杂度。假设函数partition每次选择的中间值都位于分区后的数组的中间位置，那么第1次函数partition需要扫描长度为n的数组，第2次需要扫描长度为n/2的子数组，第3次需要扫描长度为n/4的数组，重复这个过程，直到子数组的长度为1。由于n+n/2+n/4+…+1=2n，因此总的时间复杂度是O（n）。
  • 空间复杂度：O(1)

堆排序

建立大小为k的小根堆，堆顶元素就是第k大的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    // 小根堆操作：将以节点 i 为根的子树进行小根堆调整
    void minHeapify(vector<int>& nums, int i, int heapSize){
        // 获取左右子节点索引和当前节点索引
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int smallest = i;
        // 如果左子节点存在且小于当前节点，则更新最小节点索引
        if(left < heapSize && nums[left] < nums[smallest]){
            smallest = left;
        }
        // 如果右子节点存在且小于当前节点或左子节点，则更新最小节点索引
        if(right < heapSize && nums[right] < nums[smallest]){
            smallest = right;
        }
        // 如果最小节点索引不等于当前节点索引，则交换当前节点和最小节点，并继续调整最小堆
        if(smallest != i){
            swap(nums[i], nums[smallest]);
            minHeapify(nums, smallest, heapSize);
        }
    }
    // 建立小根堆
    void buildMinHeap(vector<int>& nums, int heapSize){
        // 从最后一个非叶子节点开始，依次向前调整节点，保证以每个节点为根的子树都是小根堆
        for(int i = heapSize / 2; i >= 0; i--){
            minHeapify(nums, i ,heapSize);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        // 构建一个大小为K的最小堆
        buildMinHeap(nums, k);
        for(int i = k; i < n; i++){
            if(nums[i] > nums[0]){
                swap(nums[i], nums[0]);
                minHeapify(nums, 0, k);
            }
        }
        return nums[0];
    }
};
CPP
  • 时间复杂度：建堆的复杂度为O(n)，调整堆的复杂度为O(logk)，故时间复杂度为O(nlogk)。
  • 空间复杂度：递归调用的最大深度为 logk。所以空间复杂度为 O(logk)。

LCR077.链表排序

分析

由于题目没有限定数字的范围，因此计数排序就不太适合。但可以考虑使用插入排序、冒泡排序等算法对链表进行排序，这些算法比较直观，实现起来也比较简单。只是这些算法的时间复杂度是O（n2），未必是最高效的算法。

接下来考虑对数组进行排序的时间复杂度为O（nlogn）的排序算法，常用的有堆排序、快速排序和归并排序。

如果输入的是一个数组，那么堆排序用数组实现最大堆，该排序算法每次取出其中的最大值，再调整剩余的最大堆，直到所有数字都被取出。

在数组中只需要O（1）的时间就能根据下标找到一个数字，但在链表中需要O（n）的时间才能根据节点的编号找到对应的节点。因此，不可能直接利用链表实现堆排序，但是如果链表的长度为n就可以创建一个长度为n的数组来实现堆，也就是说，通过O（n）的空间代价来实现堆排序。

接下来考虑快速排序。通常，快速排序算法首先随机生成一个下标，并以该下标对应的值作为中间值进行分区。如果输入的是数组，那么只需要O（1）的时间就能根据下标找到一个数字。但如果输入的是链表，那么需要O（n）的时间才能根据节点的编号找到对应的节点。快速排序也可以考虑不用随机的中间值，而是始终以某个固定位置的值作为中间值（如链表的头节点或尾节点），这样可能会出现每次分区时两个子链表的大小都不均衡，从而使时间复杂度退化为O（n2）。因此，虽然可以用快速排序算法对链表进行排序，但不如对数组排序高效。

那么归并排序是否适合链表？归并排序的主要思想是将链表分成两个子链表，在对两个子链表排序后再将它们合并成一个排序的链表。这看起来没有什么问题，所以可以尝试基于归并排序算法对链表进行排序。使用递归可以实现链表的归并排序，首先使用 split 函数将链表分为前后两半并返回后半部分的头节点。再将链表分成的两半使用递归实现排序，之后调用 merge 函数将两个已排序链表进行合并。其中 split 函数可以使用快慢指针法，而 merge 函数可以使用双指针法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 将链表分成两部分
    ListNode* split(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        // 前半部分列表的最后一个结点的next指针指向空
        ListNode* second = slow->next;
        slow->next = NULL;
        return second;
    }
    ListNode* merge(ListNode* head1, ListNode* head2){
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(head1 && head2){
            if(head1->val < head2->val){
                cur->next = head1;
                head1 = head1->next;
            }
            else{
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        cur->next = (head1 == NULL) ? head2 : head1;
        return dummy->next;
    }
    ListNode* sortList(ListNode* head) {
        // 递归结束
        if(!head || !head->next){
            return head;
        }
        // 将链表分成两部分
        ListNode* head1 = head;
        ListNode* head2 = split(head);
        // 将两个链表排序
        head1 = sortList(head1);
        head2 = sortList(head2);
        // 将两个链表合并
        return merge(head1, head2);
    }
};
CPP

突然发现力扣可以自己分析算法复杂度了！

  • 时间复杂度：O（nlogn）。
  • 空间复杂度：由于对链表进行归并排序不需要创建另外一个相同大小的链表来保存合并之后的节点，因此对链表进行归并排序的空间效率更高。由于代码存在递归调用，递归调用栈的深度为O（logn），因此空间复杂度为O（logn）。如果改用迭代的代码实现上述归并排序的过程，那么可以将空间复杂度优化到O（1）。

LCR078.合并K个升序链表

利用最小堆选取值最小的节点

这道题有个很朴素的想法，使用 k 个指针分别指向链表的头节点，每次都从这 k 个节点中选取值最小的节点确定为合并后的链表的第一个节点。然后将指向最小值节点的指针向后移动一步，再比较这 k 个节点中选取值最小的节点确定为下一个节点。重复以上过程，所有链表就会被合并。

这个思路需要反复比较 k 个节点的值，因为只关心值最小的节点，所以可以使用最小堆优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 最小堆
        auto cmp = [&](const ListNode* lhs, const ListNode* rhs){
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);

        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        // 将每个链表的头结点加入最小堆
        for(auto& node : lists){
            if(node){
                heap.push(node);
            } 
        }
        // 不断取堆顶元素加到结果链表中
        while(!heap.empty()){
            ListNode* node = heap.top();
            heap.pop();
            if(node->next){
                heap.push(node->next);
            }
            cur->next = node;
            cur = cur->next;
        }
        return dummy->next;
    }
};
CPP
  • 时间复杂度：假设k个排序链表总共有n个节点。如果堆的大小为k，那么空间复杂度就是O（k）。每次用最小堆处理一个节点需要O（logk）的时间，因此这种解法的时间复杂度是O（nlogk）。
  • 空间复杂度：最小堆最多存储k个元素，即空间复杂度为O(k)。

按照归并排序的思路合并链表

输入的k个排序链表可以分成两部分，前k/2个链表和后k/2个链表。如果将前k/2个链表和后k/2个链表分别合并成两个排序的链表，再将两个排序的链表合并，那么所有链表都合并了。合并k/2个链表与合并k个链表是同一个问题，可以调用递归函数解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 合并多个链表
    ListNode* mergeLists(vector<ListNode*>& lists, int start, int end){
        if(start == end){
            return lists[start];
        }
        int mid = (start + end) / 2;
        ListNode* head1 = mergeLists(lists, start, mid);
        ListNode* head2 = mergeLists(lists, mid+1, end);
        return merge(head1, head2);
    }
    // 合并两个链表
    ListNode* merge(ListNode*head1, ListNode* head2){
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(head1 && head2){
            if(head1->val < head2->val){
                cur->next = head1;
                head1 = head1->next;
            }
            else{
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        cur->next = (head1 == NULL) ? head2 : head1;
        return dummy->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0){
            return NULL;
        }
        return mergeLists(lists, 0, lists.size() - 1);
    }
};
CPP
  • 时间复杂度：递归调用的深度是O（logk），每次需要合并n个节点，因此时间复杂度是O（nlogk）。
  • 空间复杂度：O（logk），用来维护递归调用栈。

总结

如果整数在一个有限的范围内，那么可以先统计每个整数出现的次数，然后按照从小到大的顺序根据每个整数出现的次数写入输出数组中。如果n个整数的范围是k，那么计数排序的时间复杂度是O（n+k）。当k较小时，计数排序是非常高效的排序算法。

快速排序随机地从数组中选取一个中间值，然后对数组分区，使比中间值小的数值都位于左边，比中间值大的数值都位于右边，接下来将左右两边的子数组分别排序即可。快速排序的平均时间复杂度是O（nlogn）。

快速排序的函数partition可以用来选取第k大的数值。

归并排序将输入数组分成两半，在分别将左右两个子数组排序之后再将它们合并成一个排序的数组。归并排序的时间复杂度是O（nlogn），空间复杂度是O（n）。

算法笔记 > 排序
#剑指Offer
LCR074-LCR078排序
http://example.com/2024/06/01/posts/LCR074/
作者
Xuan Yang
发布于
2024年6月1日
许可协议