code排序篇

力扣912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

快速排序和归并排序

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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // qsort(nums, 0, nums.size()- 1);
        // merge_sort(nums, 0, nums.size()- 1);
        return nums;
    }

    void qsort(vector<int>& q, int l, int r)
    {
        if (l >= r) return ;

        int x = q[(l + r) >> 1], i = l - 1, j = r + 1;
        while(i < j)
        {
            do i ++ ; while(q[i] < x);
            do j -- ; while (q[j] > x);
            if (i < j)
            {
                int t = q[i];
                q[i] = q[j];
                q[j] = t;
            }
        }
        qsort(q, l, j);
        qsort(q, j + 1, r);
    }

    void merge_sort(vector<int>& q, int l, int r)
    {
        if (l >= r) return;

        int mid = (l + r) / 2;

        merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

        vector<int> tmp(r - l + 1);
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
            else tmp[k ++ ] = q[j ++ ];
        while(i <= mid) tmp[k ++ ] = q[i ++ ];
        while (j <= r) tmp[k ++ ] = q[j ++ ];
       // 每次递归，tmp都是从0开始的
        for (int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
    }
};

堆排序(大根堆和小根堆)

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
void heap(vector<int>& nums)
{
    // 为了方便使用 1-based 索引，在前面插入一个无用的数
    nums.insert(nums.begin(), -1);
    int n = nums.size() - 1;

    // 建堆（小根堆）
    for (int i = n / 2; i; i--) down(nums, i, n);
    for (int i = n; i > 1; i--)
    {
        swap(nums[1], nums[i]);
        down(nums, 1, i - 1);
    }
    // 去掉哨兵元素（还原为 0-based 数组）
    nums.erase(nums.begin());
    reverse(nums.begin(), nums.end());
}


void down(vector<int>& nums, int u, int size)
{
    int t = u;
    if (u * 2 <= size && nums[u * 2] < nums[t]) 
        t = u * 2;
    if (u * 2 + 1 <= size  && nums[u * 2 + 1] < nums[t]) 
        t = u * 2 + 1;
    if (u != t)
    {
        swap(nums[t], nums[u]);
        down(nums,t,size);
    }
}

🧠需要注意一点就是，算法模板是从小到大输出最小的数，但整个的堆并不是有序的，所以需要加上下面的这段代码

1
2
3
4
5
for (int i = n; i > 1; i--)
{
    swap(nums[1], nums[i]);
    down(nums, 1, i - 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
void heap(vector<int>& nums)
{
    nums.insert(nums.begin(), -1);   // 下标从1开始
    int n = nums.size() - 1;
    
    // 建立大根堆
    for (int i = n / 2; i; i -- ) down(nums, i, n);
    
    for (int i = n; i > 1; i -- )
    {
        swap(nums[1], nums[i]);
        up(nums, 1, i - 1);
	}
    num.erase(nums.begin());
}

void down(vector<int>& nums, int u, int size)
{
    int t = u;
    if (u * 2 <= size && nums[u * 2] > nums[t]) t = u * 2;    
    if (u * 2 + 1 <= size && nums[u * 2 + 1] > nums[t]) t = u * 2 + 1;
    
    if (u != t)
    {
        swap(nums[u], nums[t]);
        down(nums, t, size);
    }
}

这里忒一些容器的知识

1
2
3
4
5
std::vector<数据类型> 变量名;
std::vector<int> s;
std::vector<int> s{1,2,3};
std::vector<int> s(5);  // 设置了5个大小的容器
std::vector<int> s(5,100);  // 这个容器拥有五个元素，每个元素的初始值为100

容器的几个新用法：

1
2
3
4
5
6
7
8
std::vector<int> s;
s.push_back(值);  //将值添加到容器末尾
s.pop_back();  //将末尾的值删除掉
s.insert(s.begin()+2, 2); // 在指定位置插入元素
s.assign(10,100); //将s重新初始化为拥有10个元素  每个元素位100的容器
s.erase(s.begin() + 2);   // 删除指定位置的元素
s.clear(); // 将容器清空
s.empty(); //看看是不是空的

容器比数组更灵活，排序的时候可以当做数组来操作！！！

力扣56. 合并区间

ACM模式

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;
    
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for(auto seg : segs)
        if(ed < seg.first)
        {
            if (st!=-2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    
    if(st != -2e9) res.push_back({st, ed});
    
    segs = res;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    vector<PII> segs;
    for(int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }
    
    merge(segs);
    
    cout << segs.size() << endl;
    
    return 0;
}

核心代码模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 此题全为非负数，所以st  ed   设置为-1即可
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(res.begin(),res.end());

        int st = -1, ed = -1;

        for(int i = 0; i < intervals.size(); i ++ )
            if(ed < intervals[i][0])
            {
                if(st != -1) res.push_back({st, ed});
                st = intervals[i][0], ed = intervals[i][1];
            }
            else ed = max(ed, intervals[i][1]);

        if(st != -1) res.push_back({st, ed});

        return res;
    }
};

力扣148. 排序链表

方案一：开一个数组，把链表的值复制到数组里面进行排序，排序完成后再把值复制到链表里面

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
/**
 * 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* sortList(ListNode* head) {
        if(!head) return head;
        vector<int> a;
        auto p = head;
        while(p != NULL){
            a.push_back(p->val);
            p = p->next;
        }
        delete p;
        // sort(a.begin(), a.end());
        qsort(a, 0, a.size() - 1);
        auto q = head;
        for(const auto &c : a){
            q->val = c;
            q = q->next;
        }
        delete q;
        
        return head;
    }
    void qsort(vector<int> &a, int l, int r)
    {
        if (l >= r) return ;

        int i = l - 1, j = r + 1, x = a[l + r >> 1];

        while (i < j)
        {
            do i ++ ; while (a[i] < x);
            do j -- ; while (a[j] > x);
            if (i < j)
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        qsort(a, l, j);
        qsort(a, j + 1, r);
    }
};
// 使用自己写的快排，效率提升了 10% 以上

力扣179. 最大数（仅仅排序解决不了）

现在能想到的就是 如果最高位不同，那么根据最高位进行排序，如果最高位相同则比较下一位，依次类推