数组a[n]中a[0:k]a[k+1:n]倒置空间o(1)最坏时间复杂度o(n) - C++教室 - C++论坛

编程论坛 → 开发语言 → C++论坛 → 『 C++教室』 → 数组a[n]中a[0:k]a[k+1:n]倒置空间o(1)最坏时间复杂度o(n)

标题：数组a[n]中a[0:k]a[k+1:n]倒置空间o(1)最坏时间复杂度o(n)

只看楼主

落花无情

等　级：新手上路
帖　子：1
专家分：0
注　册：2008-10-1

楼主

问题点数：0 回复次数：4

数组a[n]中a[0:k]a[k+1:n]倒置空间o(1)最坏时间复杂度o(n)

出来乍到，多多关照

搜索更多相关主题的帖子: 空间　倒置　时间　

2008-10-01 15:42

守鹤

来　自：山東臨沂
等　级：贵宾
威　望：12
帖　子：337
专家分：0
注　册：2008-6-20

第 2 楼

得分:0

LZ所说的倒置是
前K个数与后面的数交换吗，那么应该是O(n),执行次数为K 或K+1

多少个日日夜夜想起你，只希望有缘再次相见

2008-10-01 16:13

yuki

等　级：新手上路
威　望：5
帖　子：508
专家分：0
注　册：2005-2-4

第 3 楼

得分:0

数列：x[] = [a][b][c][d][e][f][g]...[?] (长度n) 临时变量[]
1. set i = 0, j = n - 1
2. x[i] ==> []
3. x[j] ==> x[i]
4. [] ==> x[j]
5. i++, j--
6. i < j goto 1
7. end

我们都在命运湖上荡舟划桨，波浪起伏使我们无法逃离孤行；如果我们迷失方向，波浪将指引我们穿过另一天曙光

2008-10-01 19:43

leeco

等　级：贵宾
威　望：10
帖　子：1026
专家分：177
注　册：2007-5-10

第 4 楼

得分:0

这题目有点意思，顶一下

2008-10-03 20:38

nuciewth

来　自：我爱龙龙
等　级：贵宾
威　望：104
帖　子：9786
专家分：208
注　册：2006-5-23

第 5 楼

得分:0

[bo][un]守鹤[/un] 在 2008-10-1 16:13 的发言：[/bo]

LZ所说的倒置是
前K个数与后面的数交换吗，那么应该是O(n),执行次数为K 或K+1

貌似你不能确定后面就是K个数。

倚天照海花无数，流水高山心自知。

2008-10-03 20:42

参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-236011-1-1.html