算法Basic-排序二分

Posted on Edited on In Views:

  • 课上：理解主要思想；

  • 课后：背过，针对题目进行模板默写；

  • 熟练度练习：AC之后，删除然后重写，重复3~5次。

快速排序算法模板：

  • 步骤：1.随便找一个x； 2.二分数组，使得左边的的小于x，右边的大于x。3. 递归。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void quick_sort(int q[], int l, int r)
    {
        if (l >= r) return;

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

    作者：yxc
    链接：https://www.acwing.com/blog/content/277/
    来源：AcWing
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

786. 第k个数：快速选择算法

https://www.acwing.com/problem/content/description/788/

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少

思路：使用快排，但是我们只找第k个数，所以选择划分点k，根据k划分左右两边，判断左边得长度left<=k,那么递归计算左边便可，否则k在右边，递归计算右边，同时k更新k为k减去左边得长度。

时间复杂度为$O(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
#include <iostream>
using namespace std;
const int N = 1e6+10;
int q[N];
int n, k;

int quick_select(int l,int r, int k)
{
    //相等且第k个在中间，则答案得到
    if (l == r) return q[l];
    int i = l - 1, j = r + 1, x = q[l];
    while(i < j)
    {
        while(q[++i] < x) ;
        while(q[--j] > x) ;
        if (i < j) swap(q[i], q[j]);
    }
    
    int sl = j - l + 1; //左半部分有多少个数
    if (k <= sl) return quick_select(l, j, k);
    else
    {
        return quick_select(j + 1, r, k - sl);
    }
}
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++) scanf("%d", &q[i]);
    int ans = quick_select(0, n-1, k);
    printf("%d", ans);
}

https://www.acwing.com/problem/content/787/

归并排序模板：

  • （辅助数组）1. 找出中点位置； 2. 递归； 3. 归并—-合二为一； 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    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 ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

788. 逆序对的数量

https://www.acwing.com/problem/content/790/

  • 归并排序的时候，1、把数组切成两半；2、对左右两半做递归；3、利用辅助数组挨个放置左右部分的数字

在第三步的时候，就可以计算逆序对，特别当右部分的数放入时，与它可以构成的逆序对=左边部分的长度 - 放入的索引值。（都大于该放入值，且原本在该放入值的左边）

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
#include <iostream>
using namespace std;

typedef long long LL;

const int N =  100010;
int n;
int q[N], tmp[N];

LL merge_sort(int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    
    // 归并的过程
    int i = l , j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k++] = q[i++]; //逆序对严格大于后面的数
        else
        {
            tmp[k++] = q[j++];
            res += mid - i + 1; //从右半部分插入到左边最终位置，那么比它大的逆序对数目为左半部分长度减去它的所在位置；
        }
    }
    
    //扫尾过程
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    
    //物归原主: i是原数组，j是临时数组；
    for(int i=l, j = 0; i<=r; i++, j++) q[i] = tmp[j];
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &q[i]);
    cout << merge_sort(0, n - 1) << endl;
}

二分

整数二分算法模板：

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
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

789. 数的范围

https://www.acwing.com/problem/content/791/

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

1
2
>1 2 2 3 3 4

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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int arr[N];
int n, q;

void binary_search(int arr[], int l, int r, int query)
{
    int i = l, j = r;
    while(l < r)
    {
        int mid = l + r >> 1;
        if (arr[mid] >= query) r = mid; //check: arr[mid] >= x,使得左半部分都小于或等于x，该等于发生在左半部分的最右边处，因此r=mid,那么l =  mid + 1。
        else l = mid + 1;
    }
    //结束时l应该>=3,否则没有找到元素
    if (arr[l] != query)
        cout <<"-1 -1" << endl;
    else
    {
        cout << l << " ";
        while(i < j)
        {
            int mid = i + j + 1 >> 1;
            if (arr[mid] <= query) i = mid;  //check: arr[mid] <= x，对的右半部分都大于等于x，该等于发生在右半部分的最左边，那么i=mid,因此r = mid - 1.
            else j = mid - 1;
        }
        cout << i << endl;
    }
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    while(q--)
    {
        int query; 
        scanf("%d", &query);
        binary_search(arr, 0, n - 1, query);
    }
    return 0;
}

790. 数的三次方根

https://www.acwing.com/problem/content/submission/code_detail/405694/

  • 浮点数二分：要求保留小数后6位，那么计算的时候写r - l > 1e-8。判断时候低两位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

void cubeRoot(double n)
{
    double l = -10000, r = 10000, mid;
    
    while(r - l > 1e-8)
    {
        mid = (r + l) / 2;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%lf\n", l);
}
int main()
{
    double n;
    scanf("%lf", &n);
    cubeRoot(n);
}
iner'); }, window.Gitalk);