m********q
发帖数: 2 | 1 到底有没有time o(n)and space o(1)的solution 呀？
Given an array of positive and negative integers, re-arrange it so that
you have postives on one end and negatives on the other, BUT retain the
original order of appearance.
For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15 | y**i
发帖数: 1112 | 2 我只会这个，时间度不好：
void SplitPN(int A[], int p, int r)
{
int i = p-1, j, k, temp;
for (j = p; j <= r; ++j)
{
if (A[j] < 0)
{
++i;
for (k = j; k > i; --k)
{
temp = A[k];
A[k] = A[k-1];
A[k-1] = temp;
}
}
}
}
有谁能给个更好的？学习一下 | o**********t
发帖数: 406 | 3 如果可以申请多一倍空间，就是 O(N) 问题。只需要循环一次 | f*k
发帖数: 95 | 4 想不到
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| z****g
发帖数: 1978 | 5 void Sort(std::list& in)
{
if( !in.size() )
return;
size_t r = 0;
std::list::iterator it = in.begin();
do
{
if( *it < 0 )
{
in.push_back(*it);
in.erase(it++);
}
else
++it;
}while( ++r < in.size() );
}
应该符合要求，只扫描一遍 | z****g
发帖数: 1978 | 6 其实还有更简单的
假设数据存在list a里
bool IsNegaitve(int left, int right){ return left<0 && right>0; };
a.sort();
这个应该就可以了，原理上是nlog(n)的全排序，但是因为只有left<0, right>0才是正
序，所以应该是n要快 | o**********t
发帖数: 406 | 7 题目问的是 array 不是 linkedlist, which is super easy.
【在 z****g 的大作中提到】
: void Sort(std::list& in)
: {
: if( !in.size() )
: return;
: size_t r = 0;
: std::list::iterator it = in.begin();
: do
: {
: if( *it < 0 )
: {
| o**********t
发帖数: 406 | 8 不能 sort，否则 -3, -5, 1 会变成 -5, -3， 1
【在 z****g 的大作中提到】
: 其实还有更简单的
: 假设数据存在list a里
: bool IsNegaitve(int left, int right){ return left<0 && right>0; };
: a.sort();
: 这个应该就可以了，原理上是nlog(n)的全排序，但是因为只有left<0, right>0才是正
: 序，所以应该是n要快
| z****g
发帖数: 1978 | 9 删除插入数据算复杂度?
这个和数据结构无关吧
其实就是扫描一遍，把负的直接扔到最后一个或第一个
【在 o**********t 的大作中提到】
: 题目问的是 array 不是 linkedlist, which is super easy.
| z****g
发帖数: 1978 | 10 你看我定义的operator，你把operator定义成只有left<0, right>0才是weaker order
，其他都是
non-weak order就可以了。
【在 o**********t 的大作中提到】
: 不能 sort，否则 -3, -5, 1 会变成 -5, -3， 1
| | | o**********t
发帖数: 406 | 11 删除插入数据算复杂度？当然！！
这种 interview，你用 std::list，人家马上会追问， std::list 是怎么实现的？
【在 z****g 的大作中提到】
: 删除插入数据算复杂度?
: 这个和数据结构无关吧
: 其实就是扫描一遍，把负的直接扔到最后一个或第一个
| z****g
发帖数: 1978 | 12 你std::list里放指针不就行了，本来就是双向链表链来链去的，有什么复杂度，都是
赋值而已。说的好像你swap两个元素不用赋值
【在 o**********t 的大作中提到】
: 删除插入数据算复杂度？当然！！
: 这种 interview，你用 std::list，人家马上会追问， std::list 是怎么实现的？
| m****n
发帖数: 589 | 13 有的
扫描一遍就够了
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| o**********t
发帖数: 406 | 14 You are using an advanced data structure, which is going to need extra space
, depends on the size of data you are working with.
Pointers need space too.
The questions is simple array, constant O(1) space, which I don't think it
is possible if you also want O(N) time.
Sorting is O(N*logN) , it is not about the comparer !
It is about:
1) How many loops
2) How long are the loops
3) How many times comparing operator is called --- again, not the result of
comparing operation.
You may save time by n
【在 z****g 的大作中提到】
: 你std::list里放指针不就行了，本来就是双向链表链来链去的，有什么复杂度，都是
: 赋值而已。说的好像你swap两个元素不用赋值
| f*k
发帖数: 95 | 15 链表移动元素到最后位置当然比array快。
题目本来问的就是array，你换成指针，就是o(n)的additional space
【在 z****g 的大作中提到】
: 你std::list里放指针不就行了，本来就是双向链表链来链去的，有什么复杂度，都是
: 赋值而已。说的好像你swap两个元素不用赋值
| y**i
发帖数: 1112 | 16 请教？
【在 m****n 的大作中提到】
: 有的
: 扫描一遍就够了
| y**i
发帖数: 1112 | 17 显然不能用链表，人家考你的就是数组，链表大家都会，正因为是数组才有难度
【在 z****g 的大作中提到】
: 你std::list里放指针不就行了，本来就是双向链表链来链去的，有什么复杂度，都是
: 赋值而已。说的好像你swap两个元素不用赋值
| r****o
发帖数: 1950 | 18 能否说说你的算法？
【在 m****n 的大作中提到】
: 有的
: 扫描一遍就够了
| h**6
发帖数: 4160 | | o**********t
发帖数: 406 | 20 你外面 while 里面套 for 循环作 shift，怎么 O(N) ??
【在 h**6 的大作中提到】
: 这个算法是错的，为了避免误导大家，编辑掉了。
| | | y**i
发帖数: 1112 | 21 他这个套循环应该不要紧，while循环不是每次-1，而是每次把for循环的次数都减去了
【在 o**********t 的大作中提到】
: 你外面 while 里面套 for 循环作 shift，怎么 O(N) ??
| y**i
发帖数: 1112 | 22 不懂，能解释一下么，输入参数都是什么意思啊，为什么有两个数组？
【在 h**6 的大作中提到】
: 这个算法是错的，为了避免误导大家，编辑掉了。
| h**6
发帖数: 4160 | 23 我的这个函数stringswap肯定是O(N)，也就是O(lenx+leny)
不过外层算法错了：
“首先从左起，跳过正数，找到第一串负数和第一串正数，交换这两串。然后找到第二
串负数和第二串正数，交换。最终如果右边无串或无正数串则终止。”
应该是，第一串负数和第一串正数交换之后，前两串负数合并成一串长负数，然后与下
一串正数交换。
这样一来，如果碰上+-+-+-+-+-的情况，复杂度将达到O(N^2) | f*k
发帖数: 95 | 24 how does this work on sample 1,7,-15,9,-12,15?
第一串负数 -15， 第一串正数 1，7,交换了之后 -15，7，1，9，-12，15
然后呢？
【在 h**6 的大作中提到】
: 我的这个函数stringswap肯定是O(N)，也就是O(lenx+leny)
: 不过外层算法错了：
: “首先从左起，跳过正数，找到第一串负数和第一串正数，交换这两串。然后找到第二
: 串负数和第二串正数，交换。最终如果右边无串或无正数串则终止。”
: 应该是，第一串负数和第一串正数交换之后，前两串负数合并成一串长负数，然后与下
: 一串正数交换。
: 这样一来，如果碰上+-+-+-+-+-的情况，复杂度将达到O(N^2)
| x******3
发帖数: 245 | 25 如果这个问题有解的话，岂不是说明有space o(1)的stable quicksort？
除非不用comparison也能进行partition
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| w******1
发帖数: 520 | 26 time o(n)and space o(1)的solution 呀？
1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15 | x******3
发帖数: 245 | 27 能给伪代码不
[0
【在 w******1 的大作中提到】
: time o(n)and space o(1)的solution 呀？
: 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| o**********t
发帖数: 406 | 28 space O(1) 的意思是空间需求是常数，不管是 1 还是 100，预先订好，不能因为输入
数据长短变化。就算你要 100 个变量也好，输入数据是 10000 个，还是百万，亿万，
你都不能再申请更多了。
好，回来说说你的算法。你必须记住每个负数的位置，就是说你要知道把 1 挪到 a[1]
, 而不是 a[3] 或者其他，要把 7 挪到 a[4] ... 等等。意味着针对每个负数你要额
外空间，不符合前面条件了。
还有，如果输入只有三个数是 1,7,-5，你根本不能直接把 1 挪到最后，完全毁灭题目
的要求了。
[0
【在 w******1 的大作中提到】
: time o(n)and space o(1)的solution 呀？
: 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| y**i
发帖数: 1112 | 29 那不是结果变成了-5, -12, 1, 9, 7, 15，顺序改变了，不stable了，如果这样的话，
根本不需要第一次扫描，直接用quicksort的一次partition就可以了，pivot选一个额
外的数：0。
[0
【在 w******1 的大作中提到】
: time o(n)and space o(1)的solution 呀？
: 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| s*********g
发帖数: 153 | 30 仔细想了好久，好像是可行的。
比如说，有如下简单的例子：
case1：1，2，3，4，5 -1，-2
case2：1，2，3，4，-1，-2，-3
case3：1，2，-1，-2，-3，-4
正数，负数 分明，你找了了分界线，现在开始不断的swap，可以在时间复杂度O(n)和
空间复杂度O（1），完成。
对于case1 的过程 如下：
initial array：1，2，3，4，5 ，-1，-2
step：
(1) 1,2,3,-1,-2,4，5
(2) 1,-1,-2,2,3,4，5
(3) -1,1,-2,2,3,4，5
(4) -1,-2,1,2,3,4，5
伪代码 我就省了，的确可以写出来，逻辑太麻烦了。
所以说，关键在于 把已知数组 partition 一下， 再不断的进行上述过程：
比如说：
initial array：1，2，-1，3，4，5 -2，6，7，-3，8，-4，9
从后往前找进行partition 过程
step1 第一次partition (以||表示头尾)
1，2，-1，3，4，5 -2，6，7,-3，||8，-4||，9
进行篇头的swap过程 结果： | | | o**********t
发帖数: 406 | 31 不对啊，你把伪码在纸上划划就知道了。
数组移位是可以 O(N) 的，不管移多远。
但是，partition 在哪里，几个 partition 是由负数的个数决定的。
也就是说：
1,2,3,4,5, -1 只需要分区一次，移位一次。
1,-2,3,-4,5,6 需要分区 2 次，移位 2 次。
1,-2,3,-4, 5, -6 需要分区 3 次，移位 3 次。
总的来说还是 O(N*K) k 是负数的个数。综合一下，还是 O(n*n)，不是线性的操作。
这个问题其实很简单。可以反证，如果能实现，就意味着 merge sort 不需要额外空间
--- stable sort, O(N*LogN) time, O(1) space ...可以发论文啦！
【在 s*********g 的大作中提到】
: 仔细想了好久，好像是可行的。
: 比如说，有如下简单的例子：
: case1：1，2，3，4，5 -1，-2
: case2：1，2，3，4，-1，-2，-3
: case3：1，2，-1，-2，-3，-4
: 正数，负数 分明，你找了了分界线，现在开始不断的swap，可以在时间复杂度O(n)和
: 空间复杂度O（1），完成。
: 对于case1 的过程 如下：
: initial array：1，2，3，4，5 ，-1，-2
: step：
| s*********g
发帖数: 153 | 32 不好意思，还是不很理解。
但是我这个跟负数个数无关啊？
比如说：
-1,2,3,4,-2,-3,-4,5
我分区，就是
-1，||2,3,4,-2,-3,-4||,5
然后内部swap
结果，
-1,-2,-3,-4,2,3,4,5
这个不需要4次分区啊？
【在 o**********t 的大作中提到】
: 不对啊，你把伪码在纸上划划就知道了。
: 数组移位是可以 O(N) 的，不管移多远。
: 但是，partition 在哪里，几个 partition 是由负数的个数决定的。
: 也就是说：
: 1,2,3,4,5, -1 只需要分区一次，移位一次。
: 1,-2,3,-4,5,6 需要分区 2 次，移位 2 次。
: 1,-2,3,-4, 5, -6 需要分区 3 次，移位 3 次。
: 总的来说还是 O(N*K) k 是负数的个数。综合一下，还是 O(n*n)，不是线性的操作。
: 这个问题其实很简单。可以反证，如果能实现，就意味着 merge sort 不需要额外空间
: --- stable sort, O(N*LogN) time, O(1) space ...可以发论文啦！
| s*********g
发帖数: 153 | 33 噢，可能你误解一个问题。
我说的分区，主要是每次就找到 一段由前面 多个连续的正数 后面多个连续负数组成
的区间。每次分区，只处理那一段，然后继续往前找下一个区间，进行类似的操作。这
样，遍历完数组以后，同时排序完了
【在 o**********t 的大作中提到】
: 不对啊，你把伪码在纸上划划就知道了。
: 数组移位是可以 O(N) 的，不管移多远。
: 但是，partition 在哪里，几个 partition 是由负数的个数决定的。
: 也就是说：
: 1,2,3,4,5, -1 只需要分区一次，移位一次。
: 1,-2,3,-4,5,6 需要分区 2 次，移位 2 次。
: 1,-2,3,-4, 5, -6 需要分区 3 次，移位 3 次。
: 总的来说还是 O(N*K) k 是负数的个数。综合一下，还是 O(n*n)，不是线性的操作。
: 这个问题其实很简单。可以反证，如果能实现，就意味着 merge sort 不需要额外空间
: --- stable sort, O(N*LogN) time, O(1) space ...可以发论文啦！
| o**********t
发帖数: 406 | 34 跟负数的个数以及位置有关。
1,-2,3,-4, 5, -6
分区几次呢？
【在 s*********g 的大作中提到】
: 不好意思，还是不很理解。
: 但是我这个跟负数个数无关啊？
: 比如说：
: -1,2,3,4,-2,-3,-4,5
: 我分区，就是
: -1，||2,3,4,-2,-3,-4||,5
: 然后内部swap
: 结果，
: -1,-2,-3,-4,2,3,4,5
: 这个不需要4次分区啊？
| s*********g
发帖数: 153 | 35 这个例子这么解：
第一个区：
1，-2，3，-4，||5，-6||
swap 结果
1，-2，3，-4，-6，5
第二个区：
1，-2，||3，-4，-6||,5
swap 结果
1，-2，-4，-6，3，5
第三个区：
||1,-2,-4,-6||,3,5
结果
-2，-4，-6，1，3，5
分了三个区，但时间复杂度不是O（n*n）
首先，不是遍历三回，得到的三个区，而是遍历一遍的过程中得到三个区，因为每次产
生一个区，swap结束后，下一个区的end就已经确定了，只需要往前找下个区的start。
另外，每个区的swap时间复杂度为o（k）， o(k1+k2+k3) = o(n);
【在 o**********t 的大作中提到】
: 跟负数的个数以及位置有关。
: 1,-2,3,-4, 5, -6
: 分区几次呢？
| s*********g
发帖数: 153 | 36 呵呵，我驳回我的观点，还是有问题，不是O（N），谢谢了
【在 s*********g 的大作中提到】
: 这个例子这么解：
: 第一个区：
: 1，-2，3，-4，||5，-6||
: swap 结果
: 1，-2，3，-4，-6，5
: 第二个区：
: 1，-2，||3，-4，-6||,5
: swap 结果
: 1，-2，-4，-6，3，5
: 第三个区：
| o**********t
发帖数: 406 | 37 循环一次得到 n 个区？
循环开始的时候，n 是未知。第一次循环结束，开始针对每个区进行移位，每次移位操
作是 O(n)，总共需要 n * n。
你下面的分析已经很清楚，
如果 1, -2, 3, -4, 5, -6，7，-8 需要四个区，四次移位
如果 1, -2, 3, -4, 5, -6, 7, 8 需要三个区，三次移位
如果 1，-2，3，-4，5，+6, 7, 8 需要两个区，两次移位
你的误区是以为 swap （移位）不用循环？试试这个：
[ 10 unique positive] , -1, [ another 10 unique positive], -2, [another 10]
...
clear as crystal ...take 10 min and write psuedo code u will know
【在 s*********g 的大作中提到】
: 这个例子这么解：
: 第一个区：
: 1，-2，3，-4，||5，-6||
: swap 结果
: 1，-2，3，-4，-6，5
: 第二个区：
: 1，-2，||3，-4，-6||,5
: swap 结果
: 1，-2，-4，-6，3，5
: 第三个区：
| s*********g
发帖数: 153 | 38 谢谢了！刚才想到了类似的问题，收获很大~~的确不是O（N），那么说这道题，时
间O（N），空间 O（1），类似于 鱼与熊掌，不可兼得了？:)
10]
【在 o**********t 的大作中提到】
: 循环一次得到 n 个区？
: 循环开始的时候，n 是未知。第一次循环结束，开始针对每个区进行移位，每次移位操
: 作是 O(n)，总共需要 n * n。
: 你下面的分析已经很清楚，
: 如果 1, -2, 3, -4, 5, -6，7，-8 需要四个区，四次移位
: 如果 1, -2, 3, -4, 5, -6, 7, 8 需要三个区，三次移位
: 如果 1，-2，3，-4，5，+6, 7, 8 需要两个区，两次移位
: 你的误区是以为 swap （移位）不用循环？试试这个：
: [ 10 unique positive] , -1, [ another 10 unique positive], -2, [another 10]
: ...
| o**********t
发帖数: 406 | 39 如果真的面试问这个，能现场分析到本贴里列出的所有情况，所有 pro, con, why ...
不给满分我就跟他急 :)
Cross reference Merge Sort ...yes, I think space O(1) and O(N) at same time
is impossible.
【在 s*********g 的大作中提到】
: 谢谢了！刚才想到了类似的问题，收获很大~~的确不是O（N），那么说这道题，时
: 间O（N），空间 O（1），类似于 鱼与熊掌，不可兼得了？:)
:
: 10]
| s*********g
发帖数: 153 | 40 反正是，我是10分钟内，想不出答案了。这面试题给我，我就挂了~~
..
time
【在 o**********t 的大作中提到】
: 如果真的面试问这个，能现场分析到本贴里列出的所有情况，所有 pro, con, why ...
: 不给满分我就跟他急 :)
: Cross reference Merge Sort ...yes, I think space O(1) and O(N) at same time
: is impossible.
| | | g*******y
发帖数: 1930 | 41 你这个方法我以前也想过的，确实不是O（N）
我也不知道O（N）+O（1）的解，我觉得如果有好的解的话，发个paper是没问题的
【在 s*********g 的大作中提到】
: 谢谢了！刚才想到了类似的问题，收获很大~~的确不是O（N），那么说这道题，时
: 间O（N），空间 O（1），类似于 鱼与熊掌，不可兼得了？:)
:
: 10]
| s*********g
发帖数: 153 | 42 谢谢了~
MS的面试题真的好难啊~我这水平 算是遥遥无期了~
【在 g*******y 的大作中提到】
: 你这个方法我以前也想过的，确实不是O（N）
: 我也不知道O（N）+O（1）的解，我觉得如果有好的解的话，发个paper是没问题的
| r****o
发帖数: 1950 | 43 不好意思，能不能说说这题跟Merge Sort的关系啊，为啥说这题能用space O(1)，time
O(N)，就说明Merge Sort也能？
..
time
【在 o**********t 的大作中提到】
: 如果真的面试问这个，能现场分析到本贴里列出的所有情况，所有 pro, con, why ...
: 不给满分我就跟他急 :)
: Cross reference Merge Sort ...yes, I think space O(1) and O(N) at same time
: is impossible.
| g*******y
发帖数: 1930 | 44 觉得这个题是跟stable quicksort关联的吧
time
【在 r****o 的大作中提到】
: 不好意思，能不能说说这题跟Merge Sort的关系啊，为啥说这题能用space O(1)，time
: O(N)，就说明Merge Sort也能？
:
: ..
: time
| s*********s
发帖数: 318 | 45 两个pointer两头找.pointer是最靠近两边的+-数.只swap,用O(1) space. | o**********t
发帖数: 406 | 46 这也是我的第一个直觉，写出来才发现不是那么回事，你漏过了关键的 maintain
order of appearance.
【在 s*********s 的大作中提到】
: 两个pointer两头找.pointer是最靠近两边的+-数.只swap,用O(1) space.
| w******1
发帖数: 520 | 47
[0
我的想法是错的。次序是乱的。
【在 w******1 的大作中提到】
: time o(n)and space o(1)的solution 呀？
: 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| y**i
发帖数: 1112 | 48 我觉得也是
【在 g*******y 的大作中提到】
: 觉得这个题是跟stable quicksort关联的吧
:
: time
| B*****t
发帖数: 335 | 49 好题，只想到了time O(n), space O(sqrt(n))的算法。
不过要是所有的整数和负数分别已经排好序，就像例子中给出的那样，就可以做到
O(n) + O(1),
so that
retain the
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| b******v
发帖数: 1493 | 50 用冒泡排序，可以达到O(n^2)time和O(1)space
不过要求O(n)time，就不知道怎么做了
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| | | b******v
发帖数: 1493 | 51 如果正数负数已经排好序的情形，能否详细说说？
【在 B*****t 的大作中提到】
: 好题，只想到了time O(n), space O(sqrt(n))的算法。
: 不过要是所有的整数和负数分别已经排好序，就像例子中给出的那样，就可以做到
: O(n) + O(1),
:
: so that
: retain the
| r****o
发帖数: 1950 | 52 我发现用quick sort的partition方法的话，
能保证负数的顺序不变，但不能保证正数和0的顺序不变。
对么？
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| l*****a
发帖数: 14598 | 53 不要往quick sort上面靠拢
否则一swap，你的顺序就无法保证了
【在 r****o 的大作中提到】
: 我发现用quick sort的partition方法的话，
: 能保证负数的顺序不变，但不能保证正数和0的顺序不变。
: 对么？
| x******3
发帖数: 245 | 54 恩， 前面的partition可以保证原始顺序
【在 r****o 的大作中提到】
: 我发现用quick sort的partition方法的话，
: 能保证负数的顺序不变，但不能保证正数和0的顺序不变。
: 对么？
| a***9
发帖数: 364 | 55 这个靠谱
lz是不是您老的马甲 跟大家开愚人节玩笑呢？
随便瞎说的 别介意啊..
【在 x******3 的大作中提到】
: 如果这个问题有解的话，岂不是说明有space o(1)的stable quicksort？
: 除非不用comparison也能进行partition
| P********l
发帖数: 452 | 56 是存在o(n)time o(1)space 解法的。
分区是对的，但是我不知道怎末分区。一般要分成sqrt(n)区，选择排序每个区得到局
部有序。然后拿一个区做临时的交换区。具体的怎么做还没搞定。
这道题的答案是稳定quicksort的基础。
这道题（复杂度要求）不适合面试，没见过的基本上没戏，只有准备过的才能有思路。 | j********x
发帖数: 2330 | 57 check this paper:
http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.25.5554
Not too difficult to understand, but the method is surly not so easy to
implement. I forget how it works after reading it some 1 month ago... | P********l
发帖数: 452 | 58 search "in place merge sort"
or some discussion in stackoverflow:
http://stackoverflow.com/questions/2571049/how-to-sort-in-place
I just wonder if there is any simple solution ... | g*********s
发帖数: 1782 | 59 i don't think so. sort is a well studied problem. so it's highly
unlikely a good and simple algorithm is not well known.
i think here it's actually equivalent to stable quick sort. if a simple
stable quick sort algorithm exists, all algorithm textbooks need
revisions.
so i suggest folks not to pay too much attention to find a solution.
it's by far beyond an interview question.
back to the original problem, now i think the interviewer actually
expects you to answer the following:
"this is equivalent to a stable partition algorithm. if it exists, we
can apply it to quick sort and make quick sort stable too. but i never
see a stable quick sort algorithm. so most likely it doesn't exists, at
least not in a simple form. i'd like to share your ideas if you have
it."
the-merge-sort-algorithm
【在 P********l 的大作中提到】
: search "in place merge sort"
: or some discussion in stackoverflow:
: http://stackoverflow.com/questions/2571049/how-to-sort-in-place
: I just wonder if there is any simple solution ...
| g*********s
发帖数: 1782 | 60 btw, why u guys continue to say it's related to merge sort by stating "in-
place merge sort"?
i think "stable quick sort" is closer to its nature.
【在 g*********s 的大作中提到】
: i don't think so. sort is a well studied problem. so it's highly
: unlikely a good and simple algorithm is not well known.
: i think here it's actually equivalent to stable quick sort. if a simple
: stable quick sort algorithm exists, all algorithm textbooks need
: revisions.
: so i suggest folks not to pay too much attention to find a solution.
: it's by far beyond an interview question.
: back to the original problem, now i think the interviewer actually
: expects you to answer the following:
: "this is equivalent to a stable partition algorithm. if it exists, we
| | | a***y
发帖数: 547 | 61 There is a possible solution.
assume we have a list 2,3, -7, 4,5,-1,-2,-3
we can change it to -7,3,2,4,5,-1,-2,-3
^
then we change it to -7,2,3,4,5,-1,-2,-3
///I am not sure whether this step will bring more time complexity
then -7,-1,-2,-3,5,2,3,4
then -7,-1,-2,-3,2,3,4,5
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
| h***n
发帖数: 276 | 62 而且让merge sort stable也不难把，呵呵
【在 g*********s 的大作中提到】
: btw, why u guys continue to say it's related to merge sort by stating "in-
: place merge sort"?
: i think "stable quick sort" is closer to its nature.
| g*********s
发帖数: 1782 | 63 merge sort's weak point is not in-place.
quick sort's is not stable and worst case o(n^2).
【在 h***n 的大作中提到】
: 而且让merge sort stable也不难把，呵呵
| j******8
发帖数: 191 | 64 just give some special cases ( some might be pretty general though)
1. if max-min<(NUM_MAX-NUM_MIN)/2
or
2. if allowed at most n/16 bytes.
【在 m********q 的大作中提到】
: 到底有没有time o(n)and space o(1)的solution 呀？
: Given an array of positive and negative integers, re-arrange it so that
: you have postives on one end and negatives on the other, BUT retain the
: original order of appearance.
: For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
|
|
