差分数组 - swift

leetcode1450. 在既定时间做作业的学生人数

今天刷leetcode,一道简单的题:

image.png

题目很简单.使用数组遍历,并进行数组元素判断即可.代码如下:

func busyStudent(_ startTime: [Int], _ endTime: [Int], _ queryTime: Int) -> Int {
    var res = 0
    for i in 0..<startTime.count {
        if startTime[i]...endTime[i] ~= queryTime {
            res += 1
        }
    }
    
    return res
}

一把通过,结果如图:

image.png

然后习惯性的点击了一下官方解答,发现可以通过差分数组的方式进行解答.虽然是为了算法而去实现,但是也陷入了迷茫,为什么这种这种方式也可以实现呢?

什么是差分数组?

参考文章:什么是差分数组

比如我们现在有一个数组arr，arr={0,2,5,4,9,7,10,0}

index	0	1	2	3	4	5	6	7
arr	0	2	5	4	9	7	10	0

差分数组就是在原数组上,通过公式arr[i] - arr[i - 1]计算出来的数组.当i==0时,使用公式arr[0] - 0.
计算后结果如下表:

index	0	1	2	3	4	5	6	7
arr	0	2	5	4	9	7	10	0
公式	arr[0]-0	arr[1]-arr[0]	arr[2]-arr[1]	arr[3]-arr[2]	arr[4] - arr[3]	arr[5]-arr[4]	arr[6]-arr[5]	arr[7]-arr[6]
差分数组	0	2	3	-1	5	-2	3	-10

这么做的作用是什么呢?
现在我们需要在下标1~4范围内值全部+3,正常情况下都是遍历arr,找到指定下标,修改其中的值.操作次数和下标范围有关系.

使用差分数组,就很容易实现.也就是空间换时间的方式.
只要修改差分数组下标1的位置的值+3,并且在下标5=4+1的位置-3,即可.

index	0	1	2	3	4	5	6	7
arr	0	2+3=5	5+3=8	4+3=7	9+3=11	7	10	0
差分数组	0	2+3=5	3	-1	5	-2-3=-5	3	-10

修改差分数组后,通过差分数组求原数组中的值.

例如:差分数组[1] = arr[1]-arr[0] 那么:arr[1] = 差分数组[1]+arr[0].
修改下标1~4,可以转换成修改差分数组下标的1和4+1中的值.左+,右-

使用场景:如果arr有成百上千的元素,修改范围值也很大.并且修改次数很频繁,很多系统就会很拉胯了.
而且很多的中间结果其实并不用写回到arr中.这种情况下使用差分数组效率会很高.

使用差分数组解leetcode题目

image.png

解题思路:
一共3个学生,分别写作业的时间为:

• 1 ~ 3
• 2 ~ 2
• 3 ~ 7

求得下标4的时候,有几个学生正在写作业,用表格表示:

index	0	1	2	3	4	5	6	7
学生a		+1	+1	+1
学生b			+1
学生c				+1	+1	+1	+1	+1
arr	0	1	2	2	1	1	1	1

• index可以理解为时间
• arr数组表示当前时间下几个学生在写作业的状态.而arr[4]就是我们想要的结果.

arr数组在初始化的时候,每个元素都应该是0.有几个学生就要对arr进行几次修改,而且修改的元素个数还不一样.这时就可以使用差分数组来解决.

index	0	1	2	3	4	5	6	7
arr	0	0	0	0	0	0	0	0
cut	0	0	0	0	0	0	0	0

• cut为差分数组,根据arr数据计算得出
• 接下来我们插入学生a,1~3,看看表格中的变化

index	0	1	2	3	4	5	6	7
arr	0	0+1	0+1	0+1	0	0	0	0
cut	0	0+1	0	0	0-1	0	0	0

• 插入学生b(2~2)和

index	0	1	2	3	4	5	6	7
arr	0	1	1+1	1	0	0	0	0
cut	0	1	0+1	0-1	-1	0	0	0

• 插入学生c(3~7),由于需要计算7+1的逻辑,因此增加一列8

index	0	1	2	3	4	5	6	7	8
arr	0	1	2	1+1	0+1	0+1	0+1	0+1	0
cut	0	1	1	-1+1	-1	0	0	0	0-1

现在要求得arr[4]的值,通过表格一眼就可以看出结果.落实到代码需要通过cur来计算arr[4]

• arr[4]=cur[4]+arr[3]
• arr[3]=cur[3]+arr[2]
• arr[2]=cur[2]+arr[1]
• arr[1]=cur[1]+arr[0]
• arr[0]=cur[0]+0

最终转换arr[4] = cur[4]+cur[3]+cur[2]+cur[1]+cur[0]
也就是cur数组的前4+1的元素求和

func busyStudent(_ startTime: [Int], _ endTime: [Int], _ queryTime: Int) -> Int {
    // 获取最大结束时间
    let maxEndTime = endTime.sorted().last!
    if queryTime > maxEndTime {
        return 0
    }
    // 初始化差分数组，默认值都为0
    var cut: [Int] = Array.init(repeating: 0, count: maxEndTime + 2)
    for i in 0..<startTime.count {
        cut[startTime[i]] += 1
        cut[endTime[i] + 1] -= 1
    }
    
    var res = 0
    // 求和
    for i in 0...queryTime {
        res += cut[i]
    }
    
    return res
}