t********e 发帖数: 344 | 1 Given an array of +ve and -ve integers, re-arrange it so that u have +ves on
one end and -ves on other,BUT RETAIN ORDER OF APPEARANCE..
for eg,
1,7,-5,9,-12,15
ans=
-5,-12,1,7,9,15
do it in O(n) without using any extra space. |
t********e 发帖数: 344 | 2 我觉得明明有solution啊,就用quick sort的思想,大家看看对不对,还是我理解题目
有问题?
先扫一遍数组A[n],知道有多少负数,假设有m个
把m视为pivot的位置,设两个指针,一个初始指向A[0], 另一个初始指向A[m]:
i=0, j=m
if A[i]>0 and A[j]<0, swap them
if A[i]<0,i++
if A[j]>0,j++
直到i=m-1 或j = n-1
这样就好了是O(n) time, O(1)space
对挖? |
p*****2 发帖数: 21240 | |
l*********8 发帖数: 4642 | 4 RETAIN ORDER OF APPEARANCE
【在 t********e 的大作中提到】 : 我觉得明明有solution啊,就用quick sort的思想,大家看看对不对,还是我理解题目 : 有问题? : 先扫一遍数组A[n],知道有多少负数,假设有m个 : 把m视为pivot的位置,设两个指针,一个初始指向A[0], 另一个初始指向A[m]: : i=0, j=m : if A[i]>0 and A[j]<0, swap them : if A[i]<0,i++ : if A[j]>0,j++ : 直到i=m-1 或j = n-1 : 这样就好了是O(n) time, O(1)space
|
k*******r 发帖数: 355 | 5 如果interview时碰到这样无解的题,怎么"说服"interviewer这是无解的呢?
要是interviewer拒绝说出他心目中的答案,但就是坚持有解,那咋办? |
p*****2 发帖数: 21240 | 6
估计出这题就是想搞掉你。怎么对付听语文老师的吧。
【在 k*******r 的大作中提到】 : 如果interview时碰到这样无解的题,怎么"说服"interviewer这是无解的呢? : 要是interviewer拒绝说出他心目中的答案,但就是坚持有解,那咋办?
|
y**********u 发帖数: 6366 | 7 别,俺的烂招就成功了一次,上周onsite就没成功
这东西见仁见智,反正interview嘛,不要放在心上就好
面完了还得move on
【在 p*****2 的大作中提到】 : : 估计出这题就是想搞掉你。怎么对付听语文老师的吧。
|
c****p 发帖数: 6474 | 8 这算是面霸么?
【在 y**********u 的大作中提到】 : 别,俺的烂招就成功了一次,上周onsite就没成功 : 这东西见仁见智,反正interview嘛,不要放在心上就好 : 面完了还得move on
|
y**********u 发帖数: 6366 | 9 我过去3年好像就面了5个公司左右
【在 c****p 的大作中提到】 : 这算是面霸么?
|
c****p 发帖数: 6474 | 10 AGMFL全面过了么。。。
【在 y**********u 的大作中提到】 : 我过去3年好像就面了5个公司左右
|
|
|
p*****2 发帖数: 21240 | 11
把M换成T吧。
【在 c****p 的大作中提到】 : AGMFL全面过了么。。。
|
t********e 发帖数: 344 | 12 什么意思啊,就是order都不变?就是什么也不能做咯?
【在 l*********8 的大作中提到】 : RETAIN ORDER OF APPEARANCE
|
c****p 发帖数: 6474 | 13 太牛了。。。
【在 p*****2 的大作中提到】 : : 把M换成T吧。
|
c****p 发帖数: 6474 | 14 稳定排序
【在 t********e 的大作中提到】 : 什么意思啊,就是order都不变?就是什么也不能做咯?
|
l*****a 发帖数: 14598 | 15 跟我有一拼
热门的不敢申,不热门的不屑于申
【在 y**********u 的大作中提到】 : 我过去3年好像就面了5个公司左右
|
p*****2 发帖数: 21240 | 16
俩大牛
【在 l*****a 的大作中提到】 : 跟我有一拼 : 热门的不敢申,不热门的不屑于申
|
h********g 发帖数: 155 | 17 再某些特定情况下有解,假定k0个负数,k1个正数,
如果k=min{k0,k1}, 那么存在O(n+k^2)的算法,所以只要k=O(sqrt(n))就有O(n)算
法。 |
f***n 发帖数: 117 | 18 怎么做到O(n+K^2)?
我只能想到O(kn)的算法啊,就是假设负数少,就从最后面往前一个个找负数慢慢挪。
。。
【在 h********g 的大作中提到】 : 再某些特定情况下有解,假定k0个负数,k1个正数, : 如果k=min{k0,k1}, 那么存在O(n+k^2)的算法,所以只要k=O(sqrt(n))就有O(n)算 : 法。
|
h********g 发帖数: 155 | 19 是呀,就是从后面向前挪,先把最后一个同倒数第二个挪到一起,然后再把二个同倒数
第三个挪一起,就这样一直下去直到遇到第一个负数,然后再把所有的负数都挪到最左
边就可以了。 |
f***n 发帖数: 117 | 20 这个复杂度不是O(k^2)吧。
每次挪一个负数到前一个负数你可能要走一段距离,这段距离的上限是n,不是k吧?两
个负数的距离跟k没必然关系。
【在 h********g 的大作中提到】 : 是呀,就是从后面向前挪,先把最后一个同倒数第二个挪到一起,然后再把二个同倒数 : 第三个挪一起,就这样一直下去直到遇到第一个负数,然后再把所有的负数都挪到最左 : 边就可以了。
|
|
|
h********g 发帖数: 155 | 21 先考虑如下基本问题:
假定一个数组前N个数是正数,后M个数是负数,如何把M个负数全部移到头部,N个正数
全部移到尾部,同时不改变正数与负数的相对次序?
其实用 N+M 次交换操作就可解决上面问题。因为每次移动一个负数时,你不需要只向
前移一位,而是可以-次移很多位。
比如你有:
3 2 5 -1 -2
你可以把2与-1交换,5 与-2交换得到:
3 -1 -2 2 5
再把 3 与 -1 交换
-1 3 -2 2 5
再把 3 与 -2 交换得到
-1 -2 3 2 5
于是移位完成,用了4次交换
于是当 M 能整除 N 时, 用上面的办法其实只交换N次就可以完成了,当M不能整除N时
,你也可以用数学归纳法证明只要M+N次交换就够了。
那么现在你再回过头来看我的算法,就会发现它所需的总操作数最多是:
(l(k-1, k)+1)+(l(k-2,k-1)+2)+(l(k-3, k-2)+3)+...(l(1, 2)+k-1)+(l(0, 1)+k)
其中l(i-1, i)表示第i-1个负数和第i个负数之间所含的正数的个数,
所有的l(i-1, i) 1<=i<=k 的和最多是 N,
所以共需要O(N+k^2) 次交换操作.
【在 f***n 的大作中提到】 : 这个复杂度不是O(k^2)吧。 : 每次挪一个负数到前一个负数你可能要走一段距离,这段距离的上限是n,不是k吧?两 : 个负数的距离跟k没必然关系。
|
t********e 发帖数: 344 | 22 这题不需要排序啊……或者你是指先出现的负(正)数必须在后出现的负(正)数之前?
【在 c****p 的大作中提到】 : 稳定排序
|
t********e 发帖数: 344 | 23 望大牛明示……什么叫RETAIN ORDER OF APPEARANCE啊?
【在 p*****2 的大作中提到】 : 这题不是讨论过没解吗?
|
f***n 发帖数: 117 | 24 谢谢你这么耐烦讲解啊。不过这里还是有疑问,就是你好像没计算你寻找应该移的位置
的开销啊。我不是很确定你这里是怎么决定移到哪里的,应该也有不止一种做法,但我
想到的最直接的,就是找前一个负数,然后移到前一个负数的后面。这个开销本身可以
up to (n-k)吧。
举个例子,
3 2 -8 5 -1 -2
我会第一步把-1 -2 移到 -5的后面吧。但是你怎么知道-1前面的负数在哪里呢?没有
额外的内存来建个表的话,你就得从-1往前找,这个操作的开销最大是k1 (正数的个数
)。
也许你有更巧妙的方法来查找但是我没有理解对。
【在 h********g 的大作中提到】 : 先考虑如下基本问题: : 假定一个数组前N个数是正数,后M个数是负数,如何把M个负数全部移到头部,N个正数 : 全部移到尾部,同时不改变正数与负数的相对次序? : 其实用 N+M 次交换操作就可解决上面问题。因为每次移动一个负数时,你不需要只向 : 前移一位,而是可以-次移很多位。 : 比如你有: : 3 2 5 -1 -2 : 你可以把2与-1交换,5 与-2交换得到: : 3 -1 -2 2 5 : 再把 3 与 -1 交换
|
h********g 发帖数: 155 | 25 不客气, 你不需要建表去存储负数的位置,只需一个变量,扫一遍数组,找出最后一个
负数的位置,用该变量存储这个位置, 用O(N)时间。
然后从这个位置往后一个一个的查,查到下一个负数就是倒数第二个负数,然后用我提
到的方法把最后一个负数移到到倒数第二个负数紧接下来的位置。然后再从这个位置出
发往后找下一个负数,。。。 然后重复这一过程。
问题的关键是你从最后一个负数的位置开始向后查找,永远不需要再向前移动,而是一
直向后移,碰到下一个负数停一下,等操作完毕后继续向后移寻找下一个负数,所以最
后累计所用的时间也是O(N)。
【在 f***n 的大作中提到】 : 谢谢你这么耐烦讲解啊。不过这里还是有疑问,就是你好像没计算你寻找应该移的位置 : 的开销啊。我不是很确定你这里是怎么决定移到哪里的,应该也有不止一种做法,但我 : 想到的最直接的,就是找前一个负数,然后移到前一个负数的后面。这个开销本身可以 : up to (n-k)吧。 : 举个例子, : 3 2 -8 5 -1 -2 : 我会第一步把-1 -2 移到 -5的后面吧。但是你怎么知道-1前面的负数在哪里呢?没有 : 额外的内存来建个表的话,你就得从-1往前找,这个操作的开销最大是k1 (正数的个数 : )。 : 也许你有更巧妙的方法来查找但是我没有理解对。
|
f***n 发帖数: 117 | 26 把最后一个负数移到到倒数第二个负数紧接下来的位置。然后再从这个位置出
---->把最后一个负数移到到倒数第二个负数紧接下来的位置,这个过程的开销不是O(1
),是O(n)吧?因为不能用额外的存储,你只能暂时存一个负数 ,然后把两个负数之间
的所有数一个个挪位置,直到想要的位置空出来?
Maybe I'm missing something again.. :-) |
h********g 发帖数: 155 | 27 你应该把目光集中到累积分析上面,不要只注重一个操作所需的时间,而是所有操作所
需的时间的和。对单个操作来讲当然是O(N),但是如果把它们求和就还是O(N),因
为你从后向前操作,永远不用回头,所以操作的时间累积不会超过O(N)。
你也可以试着搜索amortized analysis,看看相关几个问题的经典分析。记得Cormen的
算法书上也有专门一章讲这个的。
(1
【在 f***n 的大作中提到】 : 把最后一个负数移到到倒数第二个负数紧接下来的位置。然后再从这个位置出 : ---->把最后一个负数移到到倒数第二个负数紧接下来的位置,这个过程的开销不是O(1 : ),是O(n)吧?因为不能用额外的存储,你只能暂时存一个负数 ,然后把两个负数之间 : 的所有数一个个挪位置,直到想要的位置空出来? : Maybe I'm missing something again.. :-)
|
f***n 发帖数: 117 | 28 我明白你的意思,但我觉得加起来是O(N*k1), k1是正数的个数。
想一个简单的worst case,所有正数在一边负数在一边,每一个正数都需要从一边挪到
另一边,而且只能一个位置一个位置的挪,这本身就是O(k1^2),对吧? amortize后不
会是O(N)啊
【在 h********g 的大作中提到】 : 你应该把目光集中到累积分析上面,不要只注重一个操作所需的时间,而是所有操作所 : 需的时间的和。对单个操作来讲当然是O(N),但是如果把它们求和就还是O(N),因 : 为你从后向前操作,永远不用回头,所以操作的时间累积不会超过O(N)。 : 你也可以试着搜索amortized analysis,看看相关几个问题的经典分析。记得Cormen的 : 算法书上也有专门一章讲这个的。 : : (1
|
v****c 发帖数: 29 | 29 要解是有解的,不过都比较复杂
做const space algo的人找简单算法找了二十多年也没找到,估计很难了
真要有人想研究这个问题,我给个reference吧
主要是两个idea
1. for blocks A and B, BA=reverse(reverse(A)reverse(B))
2. pack small int into a word
"Stable minimum space partitioning in linear time"
by Jyrki Katajainen and Tomi Pasanen
BIT Numerical Mathematics, 1992
on
【在 t********e 的大作中提到】 : Given an array of +ve and -ve integers, re-arrange it so that u have +ves on : one end and -ves on other,BUT RETAIN ORDER OF APPEARANCE.. : for eg, : 1,7,-5,9,-12,15 : ans= : -5,-12,1,7,9,15 : do it in O(n) without using any extra space.
|
t********e 发帖数: 344 | 30 好吧 想明白了 就是这个要求
我在2楼给的算法不对,是因为结果会是 -5,-12,1,9,7,15,和正确答案不一致
前?
【在 t********e 的大作中提到】 : 这题不需要排序啊……或者你是指先出现的负(正)数必须在后出现的负(正)数之前?
|