m*****f
发帖数: 1243 | 1 Given an array A of n elements and an integer k (where k
..A[k]}and {A[k+1]...A[n]} are already sorted. Give an algorithm to sort the
array A in O(n) time and O(1)space |
d**a
发帖数: 84 | 2 这个就是inplace merge吧，递归是可以，但是要用implicit stack, 不知有无别的办
法。
].
the
【在 m*****f 的大作中提到】
: Given an array A of n elements and an integer k (where k: ..A[k]}and {A[k+1]...A[n]} are already sorted. Give an algorithm to sort the
: array A in O(n) time and O(1)space
|
g*******y
发帖数: 1930 | 3 你这个题太难了，人家perfect shuffle还专门发了paper讨论O(n)time O(1)space解法，还用到了数论。
p.s.: perfect shuffle: a1a2...anb1b2...bn -> a1b1a2b2...anbn
你这个题明显比perfect shuffle又增加了难度啊。
另外, merge sort貌似就很难有in place的算法，至少我搜索过没搜索出来。 |
m*****f
发帖数: 1243 | 4 I agree, very hard...but don't blame me... This is 2008 Baidu Campus Recruit written test last question
There is a perfect solution for it. Perfect shuffle actually is the worst
case for this.
法，还用到了数论。
【在 g*******y 的大作中提到】
: 你这个题太难了，人家perfect shuffle还专门发了paper讨论O(n)time O(1)space解法，还用到了数论。
: p.s.: perfect shuffle: a1a2...anb1b2...bn -> a1b1a2b2...anbn
: 你这个题明显比perfect shuffle又增加了难度啊。
: 另外, merge sort貌似就很难有in place的算法，至少我搜索过没搜索出来。
|
g*******y
发帖数: 1930 | 5 "It has been an research interest to develop in-place mergesort algorithms, almost all of which are however inpractically complicated. "
搜到的UW CSS 342: Mathematical Principles of Computing网页上的一段话。
很好奇，百度的perfect solution是什么？
btw, perfect shuffle仅仅是这个问题的一个特例而已。搞定这个问题比搞定perfect shuffle难多了。。。因为这个问题更general啊
Recruit written test last question
【在 m*****f 的大作中提到】
: I agree, very hard...but don't blame me... This is 2008 Baidu Campus Recruit written test last question
: There is a perfect solution for it. Perfect shuffle actually is the worst
: case for this.
:
: 法，还用到了数论。
|
d**a
发帖数: 84 | 6 那到底如何回答呢？
, almost all of which are however inpractically complicated. "
【在 g*******y 的大作中提到】
: "It has been an research interest to develop in-place mergesort algorithms, almost all of which are however inpractically complicated. "
: 搜到的UW CSS 342: Mathematical Principles of Computing网页上的一段话。
: 很好奇，百度的perfect solution是什么？
: btw, perfect shuffle仅仅是这个问题的一个特例而已。搞定这个问题比搞定perfect shuffle难多了。。。因为这个问题更general啊
:
: Recruit written test last question
|
g*******y
发帖数: 1930 | 7 搜到个这个
http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
不过我没时间看了。。
【在 d**a 的大作中提到】
: 那到底如何回答呢？
:
: , almost all of which are however inpractically complicated. "
|
a********a
发帖数: 219 | 8 所以说你实在太强了。我从未见过你没听说过的题。你行的。
【在 g*******y 的大作中提到】
: 搜到个这个
: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
: 不过我没时间看了。。
|
