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 次交换操作就可解决上面问题。因为每次移动一个负数时，你不需要只向
前移一位，而是可以－次移很多位。
比如你有：
３ ２ ５ －１ －２
你可以把２与－１交换，５ 与－２交换得到：
３ －１ －２ ２ ５
再把 ３ 与 －１ 交换
－１ ３ －２ ２ ５
再把 ３ 与 －２ 交换得到
－１ －２ ３ ２ ５
于是移位完成，用了４次交换
于是当 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 次交换操作就可解决上面问题。因为每次移动一个负数时，你不需要只向
: 前移一位，而是可以－次移很多位。
: 比如你有：
: ３ ２ ５ －１ －２
: 你可以把２与－１交换，５ 与－２交换得到：
: ３ －１ －２ ２ ５
: 再把 ３ 与 －１ 交换
|
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 的大作中提到】
: 这题不需要排序啊……或者你是指先出现的负（正）数必须在后出现的负（正）数之前？
|
