Leetcode 315

这道题真的把我绕进去好久,提交也一直报错,找不出原因orz,一行一行看代码也没看出哪里有问题。栽倒了小细节上。

大概思路是用递归排序,在排序的过程中,可以更新(下标对应的)元素后面有多少个小于自己的数。
用一个新数组[0,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
43
44
45
def countSmaller(self, nums: List[int]) -> List[int]:
l = len(nums)
if l == 0:
return []
if l == 1:
return [0]
tmp = [0 for _ in range(l)]
counter = [0 for _ in range(l)]
index = [i for i in range(l)]
self.merge_sort(nums, tmp, 0, l - 1, counter, index)

return counter

def merge_sort(self, array, tmp, start, end, counter, index):
if start == end:
return
mid = (start + end) // 2
# start =0 end=1 mid=0
self.merge_sort(array, tmp, start, mid, counter, index)
self.merge_sort(array, tmp, mid + 1, end, counter, index)
if array[index[mid]] > array[index[mid + 1]]:
# 开始执行归并操作,并且在归并过程中统计出右侧小于当前元素的个数
self.sortAndCount(array, tmp, start, mid, end, counter, index)

def sortAndCount(self, array, tmp, start, mid, end, counter, index):
for i in range(start, end + 1):
tmp[i] = index[i] # 保存一下原始状态(也就是本次调用移动前的状态)

i = start
j = mid + 1
for k in range(start, end + 1):
if i > mid:
index[k] = tmp[j] # 这里的index赋值是更新移动后当前元素原来的下标(即初始数组中的位置)
j += 1
elif j > end:
index[k] = tmp[i]
counter[index[k]] += end - mid
i += 1
elif array[tmp[i]] <= array[tmp[j]]:
index[k] = tmp[i]
i += 1
counter[index[k]] += j - (mid + 1)
else:
index[k] = tmp[j]
j += 1

----本文结束啦感谢您阅读----

欢迎关注我的其它发布渠道