注册 登录
编程论坛 C++教室

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

落花无情 发布于 2008-10-01 15:42, 776 次点击
出来乍到,多多关照
4 回复
#2
守鹤2008-10-01 16:13
LZ所说的倒置是
前K个数与后面的数交换吗,那么应该是O(n),执行次数为K 或K+1
#3
yuki2008-10-01 19:43
数列: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
#4
leeco2008-10-03 20:38
这题目有点意思,顶一下
#5
nuciewth2008-10-03 20:42
[bo][un]守鹤[/un] 在 2008-10-1 16:13 的发言:[/bo]

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



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