Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit0a8119c

Browse files
Update
1 parentac17ab9 commit0a8119c

File tree

2 files changed

+5
-10
lines changed

2 files changed

+5
-10
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -214,6 +214,7 @@
214214
*[贪心算法：加油站](https://mp.weixin.qq.com/s/aDbiNuEZIhy6YKgQXvKELw)
215215
*[贪心算法：分发糖果](https://mp.weixin.qq.com/s/8MwlgFfvaNYmjGwjuMlETQ)
216216
*[贪心算法：柠檬水找零](https://mp.weixin.qq.com/s/0kT4P-hzY7H6Ae0kjQqnZg)
217+
*[贪心算法：根据身高重建队列](https://mp.weixin.qq.com/s/-2TgZVdOwS-DvtbjjDEbfw)
217218

218219

219220
* 动态规划

‎problems/0406.根据身高重建队列.md

Lines changed: 4 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -123,20 +123,14 @@ public:
123123
}
124124
};
125125
```
126-
* 时间复杂度O(nlogn + n^3)
126+
* 时间复杂度O(nlogn + n^2)
127127
* 空间复杂度O(n)
128128
129-
大家会发现这个n^3 是怎么来的？
130-
131-
其实数组的插入操作复杂度是O(n^2)：寻找插入元素位置O(1)，插入元素O(n^2)，因为插入元素后面的元素要整体向后移。
132-
133-
如果对数组的增删时间复杂度不清楚的话，可以做做这道题目[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)，数组中插入元素和删除元素都是O(n^2)的复杂度。
134-
135-
我们就是要模拟一个插入队列的行为，所以不应该使用数组，而是要使用链表！
129+
但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
136130
137-
链表的插入操作复杂度是O(n)：寻找插入元素位置O(n)，插入元素O(1)。
131+
所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n^2)了，甚至可能拷贝好几次，就不止O(n^2)了。
138132
139-
可以看出使用链表的插入效率要比普通数组高出一个数量级！
133+
对于本题，不用vector的话，如果有多少人就申请多大的固定数组来模拟插入操作也可以，这样就不会有扩充数组的情况，但是就要真的手动模拟插入的操作了，比较麻烦。
140134
141135
改成链表之后，C++代码如下：
142136

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp