今天刷leetcode,一道简单的题:
题目很简单.使用数组遍历,并进行数组元素判断即可.代码如下:
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
}
一把通过,结果如图:
然后习惯性的点击了一下官方解答,发现可以通过差分数组的方式进行解答.虽然是为了算法而去实现,但是也陷入了迷茫,为什么这种这种方式也可以实现呢?
什么是差分数组?
比如我们现在有一个数组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题目
解题思路:
一共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
}
