LeetCode + 《剑指Offer II》刷题笔记。

排序

Interval

56 Merge Intervals

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> res;
        //avoid an edge case
        res.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            int start=intervals[i][0],end=intervals[i][1];
            int lastEnd=res[res.size()-1][1];
            if(start<=lastEnd){
                //the reason of max: [1,5],[2,4]=[1,5]
                res[res.size()-1][1]=max(lastEnd,end);
            }else{
                res.push_back(vector{start,end});
            }
        }
        return res;
    }
};

时间复杂度：O(nlog n)，其中 n 为区间的数量
空间复杂度：O(log n)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。

注意1：

//avoid an edge case res.push_back(intervals[0]);

注意2：

//the reason of max: [1,5],[2,4]=[1,5]

57 Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti.

Notice:

non-overlapping intervals

intervals is sorted in ascending order by starti

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int left=newInterval[0],right=newInterval[1];
        for(int i=0;i<intervals.size();i++){
            if(right<intervals[i][0]){
                res.push_back({left,right});
                for(int j=i;j<intervals.size();j++){
                    res.push_back(intervals[j]);
                }
                return res;
            }else if(left>intervals[i][1]){
                res.push_back(intervals[i]);
            }else{
                left=min(left,intervals[i][0]);
                right=max(right,intervals[i][1]);
            }
        }
        res.push_back({left,right});
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

计数排序

1122 Relative Sort Array

Notice:

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
All the elements of arr2 are distinct.
Each arr2[i] is in arr1

本题中元素的范围为 [0, 1000]，这个范围不是很大，可以考虑不基于比较的排序，例如「计数排序」。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> res;
        vector<int> count(1001);
        for(int i=0;i<arr1.size();i++){
            count[arr1[i]]++;
        }
        for(int i=0;i<arr2.size();i++){
            while(count[arr2[i]]--){
                res.push_back(arr2[i]);
            }
        }
        for(int i=0;i<1001;i++){
            while((count[i]--)>0) res.push_back(i);
        }
        return res;
    }
};

对空间复杂度进行一个小优化。实际上，不需要使用长度为 1001 的数组，而是可以找出数组 arr1中的最大值upper，使用长度为 upper+1 的数组即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> res;
        int upper=*max_element(arr1.begin(),arr1.end());
        vector<int> frequency(upper+1);
        for(int x:arr1){
            frequency[x]++;
        }
        for(int x:arr2){
            for(int i=0;i<frequency[x];i++){
                res.push_back(x);
            }
            frequency[x]=0;
        }
        for(int x=0;x<=upper;x++){
            for(int i=0;i<frequency[x];i++){
                res.push_back(x);
            }
        }
        return res;
    }
};

时间复杂度：O(m+n+upper)
空间复杂度：O(upper)，空间复杂度可以认为是O（1）

快速排序

215 Kth Largest Element in an Array

703 Kth Largest Element in a Stream中的数据位于一个数据流中，不能一次性地将所有数据全部读入内存。而本题不一样，数据都保存在一个数组中，所有操作都在内存中完成，因此有更快找出第k大的数字的算法。

在长度为n的排序数组中，第k大的数字的下标是n-k。用快速排序的函数partition对数组分区，如果函数partition选取的中间值在分区之后的下标正好是n-k，分区后左边的值都比中间值小，右边的值都比中间值大，即使整个数组不是排序的，中间值也肯定是第k大的数字。

如果函数partition选取的中间值在分区之后的下标大于n-k，那么第k大的数字一定位于中间值的左侧，于是再对中间值左侧的子数组分区。类似地，如果函数partition选取的中间值在分区之后的下标小于n-k，那么第k大的数字一定位于中间值的右侧，于是再对中间值右侧的子数组分区。重复这个过程，直到函数partition的返回值正好是下标为n-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:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        // 第 1 大的数，下标是 n - 1;
        // 第 2 大的数，下标是 n - 2;
        // ...
        // 第 k 大的数，下标是 n - k;
        int target=nums.size()-k;
        int left=0;
        int right=nums.size()-1;
        int index=random_partition(nums,left,right);
        while(index!=target){
            if(index<target){
                left=index+1;
            }else{
                right=index-1;
            }
            index=random_partition(nums,left,right);
        }
        return nums[index];
    }
    int random_partition(vector<int>& nums,int left,int right){
        int privot=rand()%(right-left+1)+left;
        swap(nums[privot],nums[right]);
        return partition(nums,left,right);
    }
    int partition(vector<int>& nums,int left,int right){
        int small=left-1;
        for(int j=left;j<right;j++){
            if(nums[j]<nums[right]){
                //注意每次swap之前都有small++
                small++;
                swap(nums[small],nums[j]);
            }
        }
        //注意每次swap之前都有small++
        small++;
        swap(nums[small],nums[right]);
        return small;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

归并排序

148 Sort List

归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 O(logn)。如果要达到 O(1) 的空间复杂度，则需要使用自底向上的实现方式。

归并排序（递归法）

 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:
    ListNode* sortList(ListNode* head) {
        if(head==nullptr || head->next==nullptr) return head;
        ListNode* middle=middleNode(head);
        //将middle->next置nullptr是为了split分开
        ListNode* temp=middle->next;
        middle->next=nullptr;
        return mergeList(sortList(head),sortList(temp));
    }
    ListNode* middleNode(ListNode* head){
        ListNode *slow=head,*fast=head;
        //注意这里返回中间结点的第二个节点
        while(fast->next && fast->next->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    ListNode* mergeList(ListNode* front,ListNode* rear){
        ListNode* dummyHead=new ListNode(0);
        ListNode* node=dummyHead;
        while(front && rear){
            if(front->val < rear->val){
                node->next=front;
                front=front->next;
            }else{
                node->next=rear;
                rear=rear->next;
            }
            node=node->next;
        }
        node->next=(front==nullptr?rear:front);
        return dummyHead->next;
    }
};

时间复杂度 O(nlogn)
空间复杂度 O(logn)。空间复杂度主要取决于递归调用的栈空间。

归并排序（从底至顶直接合并）

时间复杂度 O(nlogn)
空间复杂度 O(1)

剑指 Offer 51. 数组中的逆序对

 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:
    vector<int> temp;
    int sum=0;
    int reversePairs(vector<int>& nums) {
        temp.resize(nums.size());
        mergeSort(nums,0,nums.size()-1);
        return sum;
    }
    void mergeSort(vector<int>& nums,int left,int right){
        if(left>=right) return;
        int mid=left+(right-left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    void merge(vector<int>& nums,int left,int mid,int right){
        for(int k=left;k<=right;k++){
            temp[k]=nums[k];
        }
        int i=left,j=mid+1;
        int index=left;
        while(i<=mid || j<=right){
            if(i>mid){
                nums[index++]=temp[j++];
            }else if(j>right){
                nums[index++]=temp[i++];
            }else if(temp[i]<=temp[j]){
                nums[index++]=temp[i++];
            }else{
                nums[index++]=temp[j++];
                sum+=(mid-i+1);
            }
        }
    }
};

时间复杂度 O(nlogn)
空间复杂度 O(n)

堆排序

23 Merge k Sorted Lists

顺序合并

逐一合并两条链表

 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


class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //注意这边res要初始化为nullptr
        ListNode* res=nullptr;
        for(ListNode* list:lists){
            res=mergeTwoList(res,list);
        }
        return res;
    }
    ListNode* mergeTwoList(ListNode* a,ListNode* b){
        if(!a || !b) return a?a:b;
        ListNode* dummyHead=new ListNode(0);
        ListNode* tail=dummyHead;
        while(a && b){
            if(a->val < b->val){
                tail->next=a;
                a=a->next;
            }else{
                tail->next=b;
                b=b->next;
            }
            tail=tail->next;
        }
        tail->next=(a?a:b);
        return dummyHead->next;
    }
};

时间复杂度 O(k^2*n)
空间复杂度 O(1)

分治合并

考虑优化顺序合并，用分治的方法进行合并。

 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


class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists,0,lists.size()-1);
    }
    ListNode* merge(vector<ListNode*>& lists,int left,int right){
        if(left==right) return lists[left];
        if(left>right) return nullptr;
        int mid=left+(right-left)/2;
        return mergeTwoList(merge(lists,left,mid),merge(lists,mid+1,right));
    }
    ListNode* mergeTwoList(ListNode* a,ListNode* b){
        if(!a || !b) return a?a:b;
        ListNode* dummyHead=new ListNode(0);
        ListNode* tail=dummyHead;
        while(a && b){
            if(a->val < b->val){
                tail->next=a;
                a=a->next;
            }else{
                tail->next=b;
                b=b->next;
            }
            tail=tail->next;
        }
        tail->next=(a?a:b);
        return dummyHead->next;
    }
};

时间复杂度 O(knlogk)
空间复杂度 O(logk) ，递归会用到 O(log k)的栈空间。

优先队列（最小堆）

用k个指针分别指向这k个链表的头节点，每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步，再比较k个指针指向的节点并选取值最小的节点。重复这个过程，直到所有节点都被选取出来。

这种思路需要反复比较k个节点并选取值最小的节点。既可以每次都用一个for循环用 O(k) 的时间复杂度比较k个节点的值，也可以将k个节点放入一个最小堆中，位于堆顶的节点就是值最小的节点。每当选取某个值最小的节点之后，将它从堆中删除并将它的下一个节点添加到堆中。

从最小堆中得到位于堆顶的节点的时间复杂度是O(1)，堆的删除和插入操作的时间复杂度是O(logk)，因此使用最小堆比直观地用for循环的时间效率更高。

 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


class Solution {
public:
    struct myComparsion{
        bool operator()(ListNode* a,ListNode* b){
            return a->val>b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,myComparsion> q;
        ListNode* dummyHead=new ListNode(0);
        ListNode* tail=dummyHead;
        for(ListNode* list:lists){
            //注意这里list的判空
            if(list){
                q.push(list);
            }
        }
        while(!q.empty()){
            ListNode* least=q.top();
            q.pop();
            tail->next=least;
            tail=tail->next;
            //注意这里least->next的判空
            if(least->next){
                q.push(least->next);
            }
        }
        return dummyHead->next;
    }
};

时间复杂度 O(knlogk)
空间复杂度 O(k) ，堆（优先队列）的大小为k。

LeetCode Sort

Table of Contents

排序