请教：最近洗衣机和烘干机的DEAL。。。谢谢！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

请教：最近洗衣机和烘干机的DEAL。。。谢谢！

请教：最近洗衣机和烘干机的DEAL。。。谢谢！# Living

a*y2012-04-27 07:04

1 楼

There is an external array of integers on which you can perform the
following operations in O(1) time.
1. get(int i) - returns the value at the index 'i' in the external array.
2. reverse( int i, int j) - returns the reverse of the array between index
positions i and j (including i and j).
example for reverse: consider an array {1,2,3,4,5}. reverse(0,2) will return
{3,2,1,4,5} and reverse(1,4) will return {1,5,4,3,2}.
Write a code to sort the external array. Mention the time and space
complexity for your code.

k*a2012-04-27 07:04

2 楼

两星期内有什么促销没？
上次BEST BUY的三星现在各涨了$100。。。
哪家有FREE SHIPPING及免费安装吗？
谢谢！

g*y2012-04-27 07:04

3 楼

insertion sort? 不过要N^2的复杂度
def reverse(alist, i, j):
if i >= j:
return alist
return alist[:i] + alist[i: j + 1][::-1] + alist[j + 1:]

def sort(alist):
for i in range(1, len(alist)):
for j in range(i - 1, -1, -1):
if alist[j + 1] < alist[j]:
alist = reverse(alist, j, j + 1)
else:
break
return alist

y*l2012-04-27 07:04

4 楼

同问
另外原来旧的怎么处理？10多年的了

【在 k****a 的大作中提到】

: 两星期内有什么促销没？
: 上次BEST BUY的三星现在各涨了$100。。。
: 哪家有FREE SHIPPING及免费安装吗？
: 谢谢！

A*l2012-04-27 07:04

5 楼

冒泡排序？ reverse(i, i+1) = swap(i, i+1)

return

【在 a*******y 的大作中提到】

: There is an external array of integers on which you can perform the
: following operations in O(1) time.
: 1. get(int i) - returns the value at the index 'i' in the external array.
: 2. reverse( int i, int j) - returns the reverse of the array between index
: positions i and j (including i and j).
: example for reverse: consider an array {1,2,3,4,5}. reverse(0,2) will return
: {3,2,1,4,5} and reverse(1,4) will return {1,5,4,3,2}.
: Write a code to sort the external array. Mention the time and space
: complexity for your code.