PeterQwQ
0%

算法

发表于 更新于 分类于

排序

快速排序

基本思路是，先选择一个基准x，然后根据这个基准来从两边进行判断，这样分成两部分，一部分比基准x小的，另一部分是比基准x长的。
然后再分别对这两边部分递归的进行快速排序，最终会得到一个排好序的数组。
时间复杂度：
最好：$O(nlogn)$ 最坏：$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quick_sort(q,l,r):
    if l >= r:
        return q
    x = q[l] 
    i = l - 1 
    j = r + 1
    while i < j:
        i = i + 1   
        while q[i] < x: 
            i = i + 1
        j = j - 1 
        while q[j] > x:
            j = j - 1
        if i < j:
            q[i],q[j] = q[j],q[i]
    quick_sort(q,l,j)
    quick_sort(q,j + 1,r)
    return q

归并排序

基本思路是，选择数组中间的点mid = (l + r) / 2，然后对于两边，递归的使用归并排序，最后把两边再合并在一起。

时间复杂度：$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge_sort(q,l,r):
    if l >= r: return [q[r]]
    mid = (l + r) >> 1
    i = l
    j = mid + 1
    merge_sort(q,l,mid)
    merge_sort(q,mid + 1,r)
    res = []
    while i <= mid and j <= r:
        if (q[i] <= q[j]) :
            res.append(q[i])
            i = i + 1
        else:
            res.append(q[j])
            j = j + 1
    while i <= mid:
        res.append(q[i])
        i = i + 1
    while j <= r:
        res.append(q[j])
        j = j + 1
    q[l:r + 1] = res
    return q

二分

给出一个排好序的数组，要求找出临界区域所在的位置。

整数二分

分为两种情况。

第一种情况，满足临界点左边区域的性质，此时此刻，应该将right更新为right = mid，左边不动。否则更新为left = mid + 1

这种情况，定义mid的时候应该定义为mid = left + right >> 1

第二种情况，满足临界点右边区域的性质，此时此刻，更新left = mid，否则更新为right = mid - 1

这种情况，定义mid的时候应该定义为mid = left + right + 1 >> 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def check():
    pass

def bsearch1(l,r):
    while l < r:
        mid = l + r >> 1
        if (check(mid)):
            r = mid
        else:
            l = mid + 1
    return r

def bsearch2(l,r):
    while l < r:
        mid = l + r + 1 >> 1
        if (check(mid)):
            l = mid
        else:
            r = mid - 1
    return r

浮点数二分

不需要处理边界，也就是不需要分情况讨论。

例如开平方的例子：

1
2
3
4
5
6
7
8
9
10
def mysqrt(x):
    l = 0
    r = x
    while (r - l > 1e-6):
        mid = (l + r) / 2
        if (mid * mid >= x): 
            r = mid
        else: 
            l = mid
    return l

需要注意的是，在x<1的时候可能会出现一些问题，例如0.01开平方之后是0.1，如果左右边界定义为0-x=0.01的时候将会找不到答案。

因此不妨把右边界定义为max(1,x)，或者可以把左右边界直接开大一点。

前缀和与差分

一维前缀和

$Si = a_1 + a_2 + … + a_i$

$S_0 = 0$

让$S_0 = 0$的目的是方便处理边界情况。

前缀和基础模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
n, m = map(int,input().split())
array = list(map(int,input().split()))
s = [0] * (n + 10)
ans = []
for i in range(n):
    s[i + 1] = s[i] + array[i]

for i in range(m):
    l, r = map(int,input().split())
    ans.append(s[r] - s[l - 1])

for i in range(len(ans)):
    print(ans[i])

二维前缀和

可以用来求一个矩阵的所有数字和。

例如需要求坐标$(x,y)$，$(a,b)$之间的矩阵的元素之和，则可以使用二维前缀和来处理。

$S = S{x,y} - S{x-1,b} - S{a,y-1} + S{a-1,b-1}$

模板：子矩阵的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n,m,q = map(int,input().split())
array = []
query = []
for i in range(n):
    array.append(list(map(int,input().split())))

for i in range(q):
    query.append(list((map(int,input().split()))))

sum = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(n):
    for j in range(m):
        sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + array[i][j]

for i in range(q):
    ans = sum[query[i][2]][query[i][3]] - sum[query[i][0] - 1][query[i][3]] - sum[query[i][2]][query[i][1] - 1] + sum[query[i][0] - 1][query[i][1] - 1]
    print(ans)

需要注意的是，Python在进行二维矩阵创建的时候可能存在“软拷贝问题”，即：

1
sum = [[0]*(m + 1)] * (n + 1)

并不能够创建一个二维数组，这将创建一个列表的列表，其中每个子列表都是对同一个列表对象的引用。这意味着修改一个子列表中的元素也会影响到其他子列表中对应位置的元素，因为它们都指向同一个对象。

而

1
sum = [[0] * (m + 1) for _ in range(n + 1)]

就可以圆满的完成所谓的创建二维矩阵。

一维差分

差分可以理解为前缀和的逆运算，用于处理某个区间内每一个数加上c这种类似的操作。

比如有个数组是$a_1,a_2,…a_n$，构造一个数组$b_1,b_2,…b_n$，使得：

即让$a1,a_2,…a_n$成为$b_1,b_2,…b_n$的前缀和数组，这样在让$a_1,a_2,…a_n$某个区间$[l,r]$的元素进行加c的操作的时候，只需要让$b_l = b_l + c,b{r+1} = b_{r + 1} - c$即可。使得时间复杂度从遍历$[l,r]$的$O(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
n,m = map(int,input().split())
array = list(map(int,input().split()))
op = []
for i in range(m):
    op.append(list(map(int,input().split())))

li = [array[0]] + [0] * (n + 10)
for i in range(1,n):
    li[i] = (array[i] - array[i - 1])

for i in range(len(op)):
    l = op[i][0] - 1
    r = op[i][1] - 1
    c = op[i][2]
    li[l] = li[l] + c
    li[r + 1] = li[r + 1] - c

ans = [0] * n
for i in range(n):
    ans[i] = ans[i - 1] + li[i]

for i in range(len(ans)):
    print(ans[i], end=" ")

但是其实在操作的时候，可以不需要对于差分数组进行构造。例如上题，我们在对于不同区间进行加c操作的时候，实际上相当于对于差分数组进行了一个插入操作。

那如果我们在一开始就将a，b数组都初始化为0，对于a数组而言，b数组理所当然是a的差分数组，因此只需要进行后续的插入即可。

因此，插入过程只需要分为两步，第一步是将a数组的元素插入，对于差分数组b而言，就是在$[i.i]$区间内插入$[a_i]$。第二步就是对于相应的要求，在不同的区间内插入值。

二维差分

和一维差分的原理一样，这里的插入公式可以写成：

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
n,m,q = map(int,input().split())
N = 1010
query = []
a = [[0]*N for _ in range(N)]
b = [[0]*N for _ in range(N)]

def insert(x1,y1,x2,y2,c):
    b[x1][y1] += c
    b[x2+1][y1] -= c
    b[x1][y2+1] -= c
    b[x2+1][y2+1] += c

for i in range(n):
        rows = list(map(int, input().split()))
        for j in range(m):
            a[i + 1][j + 1] = rows[j]

for i in range(q):
    query.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        insert(i + 1, j + 1, i + 1, j + 1, a[i + 1][j + 1])

for i in range(q):
    x1 = query[i][0]
    y1 = query[i][1]
    x2 = query[i][2]
    y2 = query[i][3]
    c = query[i][4]
    insert(x1,y1,x2,y2,c)

for i in range(n):
    for j in range(m):
        b[i + 1][j + 1] = b[i][j + 1] + b[i + 1][j] + b[i + 1][j + 1] - b[i][j] 

for i in range(n):
    for j in range(m):
        print(b[i + 1][j + 1],end=" ")
    print()