第六章 - 高频考题(困难)
1649. 通过指令创建有序数组

题目描述

1
给你一个整数数组 instructions ,你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ,你需要 从左到右 遍历 instructions 中的元素,将它们依次插入 nums 数组中。每一次插入操作的 代价 是以下两者的 较小值 :
2
3
nums 中 严格小于 instructions[i] 的数字数目。
4
nums 中 严格大于 instructions[i] 的数字数目。
5
比方说,如果要将 3 插入到 nums = [1,2,3,5] ,那么插入操作的 代价 为 min(2, 1) (元素 1 和 2 小于 3 ,元素 5 大于 3 ),插入后 nums 变成 [1,2,3,3,5] 。
6
7
请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大,请将它对 109 + 7 取余 后返回。
8
9
10
11
示例 1:
12
13
输入:instructions = [1,5,6,2]
14
输出:1
15
解释:一开始 nums = [] 。
16
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
17
插入 5 ,代价为 min(1, 0) = 0 ,现在 nums = [1,5] 。
18
插入 6 ,代价为 min(2, 0) = 0 ,现在 nums = [1,5,6] 。
19
插入 2 ,代价为 min(1, 2) = 1 ,现在 nums = [1,2,5,6] 。
20
总代价为 0 + 0 + 0 + 1 = 1 。
21
示例 2:
22
23
输入:instructions = [1,2,3,6,5,4]
24
输出:3
25
解释:一开始 nums = [] 。
26
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
27
插入 2 ,代价为 min(1, 0) = 0 ,现在 nums = [1,2] 。
28
插入 3 ,代价为 min(2, 0) = 0 ,现在 nums = [1,2,3] 。
29
插入 6 ,代价为 min(3, 0) = 0 ,现在 nums = [1,2,3,6] 。
30
插入 5 ,代价为 min(3, 1) = 1 ,现在 nums = [1,2,3,5,6] 。
31
插入 4 ,代价为 min(3, 2) = 2 ,现在 nums = [1,2,3,4,5,6] 。
32
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。
33
示例 3:
34
35
输入:instructions = [1,3,3,3,2,4,2,1,2]
36
输出:4
37
解释:一开始 nums = [] 。
38
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
39
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3] 。
40
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3,3] 。
41
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3,3,3] 。
42
插入 2 ,代价为 min(1, 3) = 1 ,现在 nums = [1,2,3,3,3] 。
43
插入 4 ,代价为 min(5, 0) = 0 ,现在 nums = [1,2,3,3,3,4] 。
44
​​​​​插入 2 ,代价为 min(1, 4) = 1 ,现在 nums = [1,2,2,3,3,3,4] 。
45
插入 1 ,代价为 min(0, 6) = 0 ,现在 nums = [1,1,2,2,3,3,3,4] 。
46
插入 2 ,代价为 min(2, 4) = 2 ,现在 nums = [1,1,2,2,2,3,3,3,4] 。
47
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。
48
49
50
提示:
51
52
1 <= instructions.length <= 105
53
1 <= instructions[i] <= 105
Copied!

前置知识

公司

  • 暂无

二分法

思路

二分法的思路比较简单,直接模拟插入即可。每次只需要保证插入之后还是有序的,这样就可以通过二分查找,计算出严格大于严格小于 x 的数目了。
  • 使用 bisect.bisect_left(nums, instruction) 可以计算出 instruction 如果插入到 nums ,instruction 在 nums 中的索引是。
  • 使用 bisect.bisect_right(nums, instruction) 和 bisect_left 类似,只不过对于 nums 已经存在 instruction 了, bisect_left 会尝试插入到其左侧,bisect_right 则会尝试插入到其右侧。
根据 bisect_left 和 bisect_right,我们就可计算出 严格大于严格小于 instruction 的数目了。接下来,我们只需要模拟插入即可。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def createSortedArray(self, instructions: List[int]) -> int:
3
mod = 10 ** 9 + 7
4
nums = []
5
ans = 0
6
# eg: 1 2 2 3
7
for instruction in instructions:
8
l = bisect.bisect_left(nums, instruction)
9
r = bisect.bisect_right(nums, instruction)
10
nums[l:l] = [instruction]
11
ans = (ans + min(l, len(nums) - r - 1)) % mod
12
return ans
Copied!
复杂度分析 令 N 为数组长度。
  • 时间复杂度:遍历 instructions 需要 $N$ 次,每次都需要插入数据, 由于插入数组的时间复杂度是 $O(N)$。 因此总的时间复杂度为 $O(N^2)$
  • 空间复杂度:$O(N)$
需要注意的是,如下代码会超时:
1
nums.insert(l, instruction)
Copied!
也就是说必须使用切片语法才可以:
1
nums[l:l] = [instruction]
Copied!
具体原因大家可以参考这个 stackoverflow 的回答

线段树(超时)

思路

这里我直接使用了计数线段树的模板。不懂线段树的可以先看下 线段树教程
我们可以维护一个 [lower,upper] 的一个线段树。线段树支持的操作:
  • query(l, r): 查询 [l, r] 范围内的数的个数
  • update(x): 将 x 更新到线段树
因此我们的目标其实就是 min(query(1, instruction - 1), query(instruction + 1, upper)),其中 upper 为 instructions 的最大树。
核心代码:
1
upper = max(instructions)
2
# 初始化线段树
3
seg = SegmentTree(upper, 1)
4
for instruction in instructions:
5
# 进行两次查询
6
l = seg.queryCount(1, instruction - 1)
7
r = seg.queryCount(instruction + 1, upper)
8
ans = (ans + min(l, r)) % mod
9
# 进行一次更新
10
seg.updateCount(instruction)
11
return ans
Copied!

代码

代码支持:Python3
Python3 Code:
1
class SegmentTree:
2
def __init__(self, upper, lower):
3
"""
4
data:传入的数组
5
"""
6
self.lower = lower
7
self.upper = upper
8
# 申请4倍data长度的空间来存线段树节点
9
self.tree = [0] * (4 * (upper - lower + 1)) # 索引i的左孩子索引为2i+1,右孩子为2i+2
10
11
# 本质就是一个自底向上的更新过程
12
# 因此可以使用后序遍历,即在函数返回的时候更新父节点。
13
def update(self, tree_index, l, r, index):
14
"""
15
tree_index:某个根节点索引
16
l, r : 此根节点代表区间的左右边界
17
index : 更新的值的索引
18
"""
19
if l > index or r < index:
20
return
21
self.tree[tree_index] += 1
22
if l == r:
23
return
24
mid = (l + r) // 2
25
left, right = tree_index * 2 + 1, tree_index * 2 + 2
26
self.update(left, l, mid, index)
27
self.update(right, mid + 1, r, index)
28
29
def updateCount(self, index: int):
30
self.update(0, self.lower, self.upper, index)
31
32
def query(self, tree_index: int, l: int, r: int, ql: int, qr: int) -> int:
33
"""
34
递归查询区间[ql,..,qr]的值
35
tree_index : 某个根节点的索引
36
l, r : 该节点表示的区间的左右边界
37
ql, qr: 待查询区间的左右边界
38
"""
39
if qr < l or ql > r:
40
return 0
41
# l 和 r 在 [ql, qr] 内
42
if ql <= l and qr >= r:
43
return self.tree[tree_index]
44
mid = (l + r) // 2
45
left, right = tree_index * 2 + 1, tree_index * 2 + 2
46
return self.query(left, l, mid, ql, qr) + self.query(right, mid + 1, r, ql, qr)
47
48
def queryCount(self, ql: int, qr: int) -> int:
49
"""
50
返回区间[ql,..,qr]的计数信息
51
"""
52
return self.query(0, self.lower, self.upper, ql, qr)
53
54
55
class Solution:
56
def createSortedArray(self, instructions: List[int]) -> int:
57
mod = 10 ** 9 + 7
58
ans = 0
59
# eg: 1 2 2 3
60
upper = max(instructions)
61
seg = SegmentTree(upper, 1)
62
for instruction in instructions:
63
l = seg.queryCount(1, instruction - 1)
64
r = seg.queryCount(instruction + 1, upper)
65
ans = (ans + min(l, r)) % mod
66
seg.updateCount(instruction)
67
return ans
Copied!
复杂度分析 令 N 为数组长度。
由于线段树更新和查询的时间复杂度为 $O(log(upper - lower))$,其中 upper 为 instructions 最大值,lower 为 instructions 最小值。由于题目限制了 $1 <= instructions[i] <= 10^5$,因此最坏情况下 upper - lower 为 10 ^5。
线段树使用了 $4 * (upper - lower + 1)$ 的空间。
  • 时间复杂度:$O(Nlog(upper-lower))$
  • 空间复杂度:$O(upper- lower)$